Problem F
Tildes

Um daginn var Bjarki að spila einn margra tölvuleikja sinna, $\sim $s. Í $\sim $s á maður að byggja sér hús og mynda sér fjölskyldu og hægt og rólega byggja sér upp auðæfi og frama. Einn daginn í leiknum var þrjátíu ára giftingaveisla, svo karakterarnir hans Bjarka buðu öllum vinum sínum og kunningjum í veislu.

Þegar að veislunni var komið fór fólk að spjalla saman. En vegna þess hvernig $\sim $s er forritaður þá hætta þeir aldrei að spjalla. Því eftir sem líður á veisluna bætist fólk inn í samtöl en slíta sig aldrei úr þeim. Hægt og rólega myndast þá hópar af fólki sem er að spjalla saman og getur enginn komist í annað samtal nema með því að sameina spjallhópana.

Nú leiðist Bjarka að fylgjast með þessu svo hann fer að telja hversu stórir spjallhóparnir eru. En hver manneskja er svo lítil á skjánum hjá honum, það er miklu auðveldara að fylgjast með talbólunum birtast þegar spjallhópar sameinast. Hann lætur þig því fá tvennskonar fyrirspurnir. Annars vegar þegar hann sér talbólu og tvo spjallhópa sameinast og hins vegar beiðni um að fá að vita hvað spjallhópur einhvers einstaklings er stór þegar hann verður forvitinn.

Inntak

Fyrsta lína inntaksins inniheldur heiltölurnar $n, q$ þ.a. $1 \leq n, q \leq 10^6$, fjöldi gesta í veislunni og fjöldi fyrirspurna frá Bjarka. Svo koma $q$ línur, hver með einni fyrirspurn. Þær eru á einu af tveimur formum. Línan getur byrjað á strengnum ‘t’ og svo tveimur heiltölum $1 \leq a, b \leq n$ sem þýðir að spjallhópar gests $a$ og gests $b$ sameinast. Ef línan byrjar ekki á ‘t’ byrjar hún á ‘s’ og fylgir þá ein heiltala $1 \leq a \leq n$ og á þá að prenta út stærð hóps gestar $a$.

Úttak

Ein lína með heiltölu $k$ fyrir hverja fyrirspurn sem byrjar á ‘s’ þar sem $k$ er stærð spjallhóps umrædds veislugestar.

10 11
t 1 10
t 1 2
t 1 3
s 1
s 2
s 3
s 4
t 5 6
s 5
s 6
s 10

4
4
4
1
2
2
4

5 11
s 1
t 1 2
s 1
t 1 2
s 1
t 4 5
s 5
t 1 5
s 2
t 3 2
s 3

1
2
2
2
4
5