Problem description
Jasio jest właśnie po przeprowadzce. Trafił z małej wioski do ogromnego miasta. Zdążył już zwiedzić całe to miasto, sporządził mapę i wybrał ważne dla siebie miejsca — np. szkoła, pizzeria, basen, nazwał je punktami zainteresowania. Jasio jest nieśmiały i nie lubi spotykać się z ludźmi — niestety, przy każdym miejscu ważnym dla niego (czyli punkcie zainteresowania) spotykają się ludzie i siłą rzeczy musi z nimi porozmawiać (co zabiera oczywiście czas i denerwuje Jasia).
Jasio chce napisać program, który powie mu na co ma się przygotować przed wyprawą do jakiegoś miejsca — chce wiedzieć ile razy będzie musiał się zatrzymywać i rozmawiać z ludźmi, innymi słowy: przez ile minimalnie punktów zainteresowania musi przejść, by dostać się do wybranego przez niego miejsca. Jasio ma ogromną ilość pytań, które chce zadać swojemu programowi. Niestety, zanim Jasio zdebugowałby swój kod, zdążyłby się znowu przeprowadzić. Dlatego poprosił Cię o pomoc — napisz ten program za niego.
Jasio zauważył, że masz ułatwione zadanie — dla każdej pary punktów zainteresowania istnieje zawsze dokładnie jedna trasa między nimi.
Napisz program, który: wczyta z wejścia opis miasta i pytania Jasia, obliczy dla każdego pytania, ile punktów zainteresowania musi pokonać Jasio, aby przedostać się z jednego miejsca do innego, wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i Q, oddzielone pojedynczym odstępem i określające kolejno: liczbę punktów zainteresowania oraz liczbę zapytań Jasia. W kolejnych N − 1 wierszach znajdują się połączenia między punktami zainteresowania. Każde takie połączenie składa się z dwóch liczb u i v, oddzielonych pojedynczym odstępem i określających numery punktów zainteresowania, między którymi można przejść bezpośrednio (bez przechodzenia między innymi punktami zainteresowania).
W kolejnych Q wierszach znajdują się pytania Jasia. W N + i-tym wierszu znajduje się i-te pytanie Jasia. Każde z pytań Jasia składa się z dwóch liczb a i b, oddzielonych pojedynczym odstępem. Są to numery punktów zainteresowania, między którymi chce się przemieścić Jasio.
Punkty zainteresowania numerowane są kolejnymi liczbami naturalnymi od 1 do N (włącznie).
Wyjście
Twój program powinien wypisać na wyjście dokładnie Q wierszy. W i-tym wierszu powinna się znaleźć odpowiedź na i-te pytanie Jasia. Odpowiedź na każde pytanie Jasia to jedna nieujemna liczba całkowita określająca minimalną ilość punktów zainteresowania, które należy pokonać, aby przemieścić się między wybranymi przez Jasia miejscami.
Ograniczenia
1 ≤ N ≤ 250 000, 1 ≤ Q ≤ 500 000.
W testach wartych łącznie 30% maksymalnej punktacji: N ≤ 2 000, M ≤ 5 000.
Przykład
| Wejście | Wyjście | |
|
|