== include(page="template/taskheader" task_id="maxdist") ==

Poveste şi cerinţă...

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.
 
h2. Cerinta
 
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.

h2. Date de intrare

Fişierul de intrare $maxdist.in$ ...

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ă.

h2. Date de ieşire

În fişierul de ieşire $maxdist.out$ ...

Fişierul de ieşire $maxdist.out$ va conţine $Q$ linii. Pe liniai, 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$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $2 ≤ N ≤ 200000$
* $1 ≤ Q ≤ N$
* $1 ≤ x, y, c ≤ 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 ≤ 1000.$
* $Pentru restul de 80% din teste, 100000 ≤ N ≤ 200000.$

h2. Exemplu
table(example). |_. maxdist.in |_. maxdist.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 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
| 5 0 5 3 5 4 4 4 4 4 4 5

|
h3. Explicaţie