Nea puiu

“Una e să te spargi în figuri, și alta e să spargi figuri”

Lui Nea Puiu îi place foarte mult să spargă figuri. În cazul de față, figurile pe care vrea să le spargă sunt arbori cu $N$ noduri care au rădăcina fixată (un arbore reprezintă un graf neorientat, conex și aciclic). Prin spargerea unui arbore se înțelege tăierea unei muchii a acestuia, fapt ce cauzează ca toate nodurile care nu mai sunt conectate cu rădăcina arborelui să se desprindă de acesta.

Înainte de a da lovitura, Nea Puiu a studiat cu atenție proprietățile arborilor și a definit adâncimea unui subarbore ca fiind cea mai mare distanță dintre rădăcina subarborelui și o frunză a acestuia.

Fiindcă Nea Puiu nu dorește să lase multe dovezi după acțiunile sale, el dorește să răspundă la întrebări de forma: ”În câte moduri poate tăia o muchie din subarborele cu rădăcina în nodul $x$ astfel încât după taiere, noua adâncime a subarborelui să fie aceeași cu adâncimea de dinainte?”.

Totuși, Nea Puiu este un profesionist, așa că se întreabă ce s-ar întampla dacă arborele s-ar modifica între diverse întrebări. Așadar, pot exista două evenimente de modificare a arborelui: fie se șterge o anumită frunză a acestuia, fie se adaugă un nod nou, legat de unul dintre nodurile deja existente în arbore.

Cerinţă

Deoarece Nea Puiu este nevoit să se ocupe de contribuțiile la gaze, voi trebuie, dându-se arborele inițial și $M$ operații de forma celor descrise mai sus, să răspundeți la întrebările acestuia!

Date de intrare

Fișierul de intrare neapuiu.in conține două numere naturale: $N$, numărul de noduri din arbore și $M$, numărul de operații ce se vor efectua.

Următoarele $N – 1$ linii descriu muchiile arborelui. Fiecare linie conține două numere naturale, $x$ și $y$, separate printr-un spațiu, reprezentând faptul ca există o muchie de la $x$ la $y$ în arbore.

Următoarele $M$ linii descriu operațiile efectuate. Fiecare linie este formată din numere naturale și poate avea unul dintre următoarele formate:

• $0$ $x$ $y$ – se adaugă nodul cu indicele $y$ ca fiu al nodului cu indicele $x$ ; se garantează că nu a mai existat niciun nod în arbore cu indicele $y$ până în momentul de față
• $1$ $x$ – se șterge nodul cu indicele $x$ – se garantează că nodul $x$ este frunză în arborele curent
• $2$ $x$ – trebuie să răspundeți la întrebarea : ”În câte moduri pot tăia o muchie din subarborele cu rădăcina în nodul $x$ astfel încât după taiere noua adâncime a subarborelui să fie aceeași cu adâncimea de dinainte?”

Date de ieşire

Fișierul de ieșire neapuiu.out va trebui să conțina răspunsurile la întrebările din fișierul de intrare, câte unul pe linie.

Restricţii si precizări

• $1 \leq N, M \leq 100.000$
• radacina arborelui este nodul $1$; se garanteaza că acest nod nu va fi șters
• se garantează că o data ce un nod este șters din arbore, nu va mai exista niciun alt nod adaugat cu același indice
• se garantează că nu vor exista două noduri cu același indice în arbore

Exemplu

neapuiu.in

9 14
1 2
1 6
2 3
2 4
4 5
6 7
6 8
6 9
2 1
2 2
0 3 10
2 2
2 6
1 8
2 6
0 9 11
0 11 12
2 6
0 7 13
1 12
2 6
2 5

neapuiu.out

5
1
4
3
2
1
4
0