4. Småland

Keďže je Kristína nadšená cestovateľka, ako už bolo niekde spomenuté, po nejakom čase sa rozhodla ísť na dlhú dovolenku do provincie Småland na juhu Švédska. Ak ste nevedeli, Småland obsahuje jeden z najväčších systémov súostroví na svete, a tým, že sa Kika celkom nudila, rozhodla sa, že prejde všetky ostrovy v ňom.

Kika nevie plávať (a na jar v Baltskom mori ani veľmi nechce), ale, naštastie, vo vyspelých severských krajinách to chodí tak, že každú chvíľu sa medzi nejakými dvomi ostrovmi postaví most, po ktorom vie prejsť. Samozrejme, nie vždy sú všetky ostrovy poprepájané, a tak súostrovie obsahuje len skupinky prepojených ostrovov.

V takto vytvorených skupinkách väčšinou bývajú takzvané špeciálne ostrovy ™, ktoré sú napojené len jedným mostom so zvyškom skupinky, a teda pokiaľ Kika na takýto ostrov príde, jej jediná možnosť je vrátiť sa po tom istom moste naspäť.

Kristína by pre potreby plánovania výletu rada vedela, koľko takých špeciálnych ostrovov vie z nejakého ostrovu navštíviť len prechádzaním po mostoch. Môže sa pohybovať ako chce a ostrovmi aj mostami môže prechádzať koľkokrát chce v ľubovoľnom smere (je predsa na dovolenke, nie na diaľnici).

Úloha

Vašou úlohou bude zisťovať, koľko špeciálnych ostrovov vie Kika dosiahnuť z ľubovoľného ostrova v závislosti od toho, aké mosty sú v danom čase postavené. Budete začínať len s izolovanými ostrovmi. Kedykoľvek môžete dostať informáciu, že sa postavil most medzi nejakými ostrovmi \(a\) a \(b\). Taktiež sa Vás kedykoľvek môže Kika spýtať, na koľko špeciálnych ostrovov sa vie z nejakého ostrovu \(x\) dostať. Informácie o mostoch a otázky o špeciálnych ostrovoch budeme súhrnne označovať queries.

Formát vstupu

V prvom riadku vstupu sú dve čísla \(n\) a \(q\). Číslo \(n\) udáva, koľko je ostrovov v súostroví, číslo \(q\) zase koľko dostanete queries.

Nasledovať bude \(q\) jednoriadkových queries, ktoré budú mať buď tvar ! a b (bol postavený most medzi ostrovmi \(a\) a \(b\)) alebo ? x (Kika sa pýta, na koľko špeciálnych ostrovov sa vie dostať z ostrovu \(x\)).

Sú 4 sady vstupov, môžete v nich predpokladať nasledujúce obmedzenia:

Formát výstupu

Na informáciu o stavbe mosta nevypisujete nič. Na otázku o špeciálnych ostrovoch vypíšte počet takýchto ostrovov.

Príklady

Input:

3 4
! 0 2
? 0
? 2
? 1

Output:

2
2
0

Vytvorili sme most medzi ostrovmi 0 a 2. Z ostrova 0 sa vieme dostať na 2 špeciálne ostrovy (vrátane toho, na ktorom stojíme). Z ostrova 1 sa nevieme dostať na žiadny špeciálny ostrov, pretože je izolovaný.

Input:

6 8
! 0 2
! 2 4
! 1 3
! 1 5
? 0
? 5
! 0 1
? 3

Output:

2
2
3

Pred prvými otázkami nám vzniknú dve skupinky ostrovov, každá má 2 špeciálne ostrovy. Potom spojíme špeciálny ostrov 0 z prvej skupinky s normálnym ostrovom 1 z druhej skupinky, čím nám vznikne veľká skupina ostrovov s 3 špeciálnymi ostrovmi.