Problem description
Wyspa Bajtocka to nieduża wyspa położona na Oceanie Bitlantyckim, która ze względu na swój rozmiar ma dosyć ubogą sieć drogową. Na wyspie znajduje się N miast, które są połączone N − 1 dwukierunkowymi drogami tak, że pomiędzy każdą parą miast da się przejachać na dokładnie jeden sposób.
Sroga zima spowodowała duże uszkodzenia nawierzchni dróg na wyspie, co zmusiło lokalne władze do zatrudnienia firmy Januszex S.A. w celu remontu Bajtockich dróg. Firma Januszex S.A., jak na prawdziwych Januszy przystało, remontuje drogi w bardzo dziwny sposób. Od czasu do czasu zaczynają naprawę ścieżki od miasta a do miasta b, która polega na tym, że remontują wszytskie drogi na ścieżce od a do b, które nie były już w tym momencie remontowane. Analogicznie firma Januszex S.A. rozumie koniec naprawy ścieżki od c do d – wszystkie drogi na ścieżce od c do d które były teraz remontowane, stają się przejezdne.
Andrzej mieszka na wyspie i ceni sobie możliwość szybkiego przejazdu między miastami. Czasami musi wyjechać w pilną podróż z miasta a do miasta b i zastanawia się ile dróg jest w danym momencie remontowanych – pozwoli mu to oszacować czas przejazdu. Napisz program, który wczyta opis wyspy i wypisze poprawne odpowiedzi na wszystkie zapytania Andrzeja.
Wejście
W pierwszej linii wejścia znajdują się dwie liczby N i Q. Oznaczają one liczbę miast na Wyspie Bajtockiej i liczbę wydarzeń.
W każdej z N − 1 kolejnych linii wejścia pojawią się dwie liczby a i b (1 ≤ a, b ≤ N), które oznaczają, że miasta a i b są połączone dwukierunkową drogą.
W każdej z kolejnych Q linii wejścia pojawia się opis jednego wydarzenia w postaci trzech liczb t, a, b (1 ≤ t ≤ 3, 1 ≤ a, b ≤ N). Jeśli t = 1 to Januszex S.A. zaczyna naprawę dróg na ścieżce od a do b. Jeśli t = 2 to Januszex S.A. zakończyło naprawę dróg na ścieżce od a do b. Natomiast jeśli t = 3 to Andrzej wyrusza w podróż z miasta a do miasta b. Wydarzenia są podane na wejściu w kolejności chronologicznej.
Wyjście
Dla każdego wydarzenia typu t = 3 wypisz jedną liczbę oznaczającą liczbę aktualnie remontowanych dróg na ścieżce od a do b. Możesz założyć, że w każdym teście będzie co najmniej jedno wydarzenie typu t = 3.
Ograniczenia
2 ≤ N ≤ 100 000, 1 ≤ Q ≤ 100 000
Przykład
| Wejście | Wyjście | |
|
|