Doi Arbori

Fie doi arbori $G$ și $H$. Arborele $G$ are nodurile $G_1, \dots , G_N$, iar arborele $H$ are nodurile $H_1, \dots , H_N$. Pentru oricare $u$ și $v$, se garantează că există o muchie între $G_u$ și $G_v$ dacă și numai dacă exista o muchie între $H_u$ și $H_v$. Toate muchiile din arborii $G$ și $H$ au lungimea $1$.

Frunzele dintr-un arbore pot fi conectate cu corespondentul lor din celălalt arbore printr-o muchie de lungime $0$. Cu alte cuvinte, pentru oricare $v$, frunza $G_v$ poate fi conectată printr-o muchie cu frunza $H_v$. Dacă frunza $G_v$ este conectată cu frunza $H_v$, atunci frunza respectivă se consideră activă, iar altfel este inactivă.

Inițial, toate frunzele sunt inactive. Avem două tipuri de operații:

• 1 v — schimbă starea frunzelor $G_v$ și $H_v$: devin active din inactive și vice-versa;
• 2 u v — se cere să se afle lungimea celui mai scurt drum de la nodul $G_u$ la nodul $H_v$.

Date de intrare

Pe prima linie a fișierului de intrare se află doi întregi $N$ și $Q$ — numărul de noduri și numărul de operații. Pe fiecare din următoarele $N − 1$ linii se află câte doi întregi $u, v \ (1 ≤ u, v ≤ N)$ — structura arborilor — muchiile $(G_u, G_v)$ și $(H_u, H_v)$.

Fiecare dintre următoarele $q$ linii descriu operațiile. Fiecare operație este fie de forma 1 v $(1 ≤ v ≤ N)$, fie de forma 2 u v $(1 ≤ u, v ≤ N)$.

Date de ieșire

Pentru fiecare operație de tipul $2$, în ordinea de la intrare, câte un întreg pe o linie — lungimea drumului minim dintre cele două noduri date. Dacă nu există un astfel de drum, se va afișa $−1$.

Restricții și precizări

• $1 \leq N, Q \leq 200 \ 000$
• Fie $K$ numărul total de operații de tipul $2$.

Exemplul 1

stdin

7 11
1 2
2 3
1 4
2 5
4 6
4 7
1 6
1 3
2 1 6
2 1 2
1 7
2 5 4
2 6 3
1 6
1 3
1 5
2 6 3

stdout

2
3
5
4
6

Explicație

Arborii $G$ și $H$ au următoarea structură.

Pentru prima interogare, structura arborelui este cea de mai jos. Un drum posibil este desenat cu roșu. Muchiile punctate au lungimea $0$.

A doua interogare apare mai jos.

A treia interogare apare mai jos.

A patra interogare apare mai jos.

Ultima interogare apare mai jos.

Exemplul 2

stdin

2 2
1 2
1 1
2 1 2

stdout

1