Bağlan və Ayır

DFS, yəni Dərinlik üzrə Axtarış metodunu bilirsinizmi?

Bu metoddan istifadə edərək, qrafın əlaqəliliyini O(E) vaxtda yoxlamaq mümkündür. Həmçinin, eyni vaxtda qrafın əlaqə komponentlərinin sayını da hesablamaq olar.

Bəs DSU, yəni Kəsişməyən Çoxluqlar Sistemi haqqında məlumatınız varmı? Bu məlumat strukturundan istifadə edərək, "Qrafa kənar əlavə et" və "Qrafın əlaqə komponentlərinin sayını hesabla" tipli sorğuları sürətlə işləyə bilərsiniz. Hər iki sorğu O(log N) vaxtda yerinə yetirilə bilər.

Dynamic Connectivity Problem haqqında nə bilirsiniz? Bu məsələdə siz 3 tipli sorğuları sürətlə işləməlisiniz:

1. Qrafa kənar əlavə et.

2. Qrafdan kənar sil.

3. Qrafın əlaqə komponentlərinin sayını hesabla.

Giriş verilənləri

Başlanğıcda qraf boşdur.

Giriş faylının ilk sətiri 2 ədəd — N və K — təpələrin sayı və sorğuların sayını (1 ≤ N ≤ 300000, 0 ≤ K ≤ 300000) ehtiva edir.

Sonrakı K sətir sorğuları, hər biri bir sətirdə olmaqla ehtiva edir. 3 tipli sorğular mövcuddur:

1. + u v: u və v təpələri arasında kənar əlavə et. Sorğu alındığı anda qrafda belə bir kənarın olmadığı təmin edilir.

2. - u v: u və v təpələri arasında kənar sil. Sorğu alındığı anda qrafda belə bir kənarın olduğu təmin edilir.

3. ?: cari anda qrafın əlaqə komponentlərinin sayını hesabla.

Təpələr 1 -dən N -ə qədər nömrələnir. u = v olan sorğular yoxdur. Qraf yönsüzdür.

Çıxış verilənləri

'?' tipli hər bir sorğu üçün, sorğu zamanı qrafın əlaqə komponentlərinin sayını ayrı bir sətirdə çıxarın.

Nümunələr