Seturi

Cerință

Se consideră un arbore cu $N$ noduri și un set de lanțuri simple $S$, inițial gol.
Se dau $Q$ operații de două tipuri:

• $1$ $x$ $y$, se adaugă in $S$ lanțul simplu de la $x$ la $y$
• $2$ $x$, să se afișeze numărul de lanțuri simple din $S$ care îl conțin pe $x$

Date de intrare

Pe prima linie se găsesc două numere întregi, $N$ și $Q$. Pe următoarele $N-1$ rânduri se găsesc perechi de numere $a$ și $b$ cu proprietatea că există muchie între $a$ și $b$ în arbore. Pe următoarele $Q$ linii se află interogările.

Date de ieșire

Se vor afișa răspunsurile pe rânduri diferite.

Restricții și precizări

• $1 \leq Q, N \leq 10^5$;
• $1 \leq a,b \leq N$;
• $1 \leq x,y \leq N$;

Exemplul 1

stdin

5 4
1 2
2 3
2 4
1 5
2 2
1 3 5
1 2 4
2 2

stdout

0
2