2. Treba vysávať

Georg sa po desaťročnej zaoceánskej plavbe vrátil do svojej vily a zistil, že po celých desať rokov v nej nikto nevysával. Tak sa do toho hneď pustil a plný energie začal vysávať, čo mohol. Ale po chvíli si všimol, že si to mal lepšie naplánovať – vo svojom zápale povysával niektoré miesta viackrát a niektoré vôbec. Teraz potrebuje vašu pomoc.

Úloha

Georgova vila má \(n\) miestností a \(n-1\) chodieb. Každá chodba spája práve dve miestnosti, a medzi každými dvoma miestnosťami vedie práve jedna cesta.

Georg postupne robí \(q\) rôznych činností – buď vysáva, alebo premýšľa. Vysáva tak, že začne v miestnosti \(a\), ide do miestnosti \(b\), a cestou povysáva každú chodbu, ktorou prejde. Premýšľa tak, že príde do nejakej chodby a snaží sa spomenúť si, koľkokrát ju už povysával. S tým mu musíte pomôcť.

Formát vstupu a výstupu

Na prvom riadku sú čísla \(n\) a \(q\) (\(1\leq n,q \leq 100\,000\)) udávajúce počet miestností a počet činností. Miestnosti sú očíslované od \(1\) po \(n\).

Nasleduje \(n-1\) riadkov, ktoré popisujú chodby. Každý obsahuje dve čísla \(p,q\) udávajúce, že miestnosti \(p\) a \(q\) sú spojené chodbou.

Ďalších \(q\) riadkov jednotlivé popisuje činnosti. Na každom sú tri čísla \(t,x,y\). Aby sme zabezpečili, že činnosti naozaj vyhodnocujete v zadanom poradí, musíte ich najprv dekódovať: Nech \(v\) je posledné číslo, čo ste zatiaľ vypísali, alebo \(0\), ak ste zatiaľ nevypísali nič. Potom nech \(a=x \verb! xor ! v\), \(b=y \verb! xor ! v\).

Keď vypočítate \(a\) a \(b\), číslo \(t\) vám povie typ činnosti, čo máte spraviť. Platí \(1\leq a,b \leq n\) a \(a\neq b\). Ak je \(t=1\), Georg povysáva všetky chodby medzi miestnosťami \(a\) a \(b\) (nemusíte nič vypísať). Ak je \(t=2\), Georg príde do chodby medzi miestnosťami \(a\) a \(b\) (určite budú spojené chodbou) a chce, aby ste vypísali jedno číslo: počet, koľkokrát ju zatiaľ povysával. (Toto číslo bude nová hodnota \(v\).)

Príklad

Input:

6 7
2 4
1 2
4 6
4 5
3 2
2 4 5
1 6 1
1 4 3
1 2 6
2 4 2
1 0 5
2 1 0

Output:

0
3
2

Na predposlednom riadku je \(a=3,b=6\). Na poslednom riadku je \(a=2,b=3\).