maxdist

Orașul Focșani este organizat sub forma unui arbore cu $N$ noduri, fiecare nod reprezentând un cartier al acestui oraș. În Focșani, există o bandă de bicicliști care se plimbă în voie prin oraș. Într-o zi, o altă bandă de bicicliști își face apariția în Focșani și începe să cucerească, câte unul pe zi, o parte din cartierele ce mai demult aparțineau primei bande de bicicliști.

La finalul unei zile, bicicliștii din ambele bande pornesc dintr-un cartier pe care îl dețin și se deplasează spre un alt cartier pe care îl dețin, fără a trece de mai multe ori prin același cartier. Întrucât bicicliștii din Focșani sunt foarte try-hard, aceștia își doresc sa parcurgă o distanță cât mai lungă în fiecare zi. Astfel, după fiecare zi în care unul din cartierele primei benzi este cucerit de a doua bandă, fiecare bandă se întreabă care e distanța maximă care se poate parcurge, alegând convenabil cartierul de pornire si cel destinație, dintre cele pe care banda le deține.

Cerință

Cunoscându-se structura orașului Focșani, un număr $Q$ de zile și ce cartier este cucerit de a doua bandă în fiecare din cele $Q$ zile, se cere distanța maximă pe care fiecare bandă o poate parcurge în cele $Q$ zile. Se consideră că, într-o zi, mai întâi are loc cucerirea unui cartier și apoi deplasarea bicicliștilor.

Date de intrare

Pe prima linie a fișierului de intrare maxdist.in se vor afla două numere naturale $N$ si $Q$, reprezentând numărul de cartiere din Focșani, respectiv numărul de zile care ne interesează. Pe următoarele $N - 1$ linii, se vor afla câte două numere naturale $x$ și $y$, reprezentând faptul că există o muchie între $x$ și $y$. Pe următoarele $Q$ linii, se va afla câte un număr natural $c$, care reprezintă cartierul cucerit de a doua bandă în ziua respectivă.

Date de ieșire

Fișierul de ieșire maxdist.out va conține $Q$ linii. Pe linia $i$, se vor afișa două numere naturale, reprezentând distanța maximă pe care o pot parcurge membrii din prima bandă, respectiv a doua bandă, după ziua $i$.

Restricții și precizări

• $2 \leq N \leq 200 \ 000$
• $1 \leq Q \leq N$
• $1 \leq x, y, c \leq N$
• Un cartier va fi cucerit o singură dată.
• Distanța dintre două cartiere este definită ca numărul de muchii dintre acestea.
• Dacă nu există cel puțin două cartiere deținute de o bandă, vom considera că distanța maximă pe care această bandă o poate parcurge este $0$.
• Bicicliștii pot trece prin cartiere ce nu aparțin bandei lor, dar nu pot să plece din acestea sau să se oprească în acestea.
• Pentru $20\%$ din teste, $N \leq 1 \ 000$.
• Pentru restul de $80\%$ din teste, $100 \ 000 \leq N \leq 200 \ 000$.

Exemplu

maxdist.in

10 6
1 2
2 3
2 8
3 4
3 5
1 6
6 7
6 9
1 10
3
6
4
5
10
9

maxdist.out

5 0
5 3
5 4
4 4
4 4
4 5