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

Se dă un 'arbore':http://en.wikipedia.org/wiki/Tree_%28graph_theory%29 cu $N$ noduri, având rădăcina în nodul $1$. Să se răspundă la $M$ întrebări de forma: "Care este 'cel mai apropiat strămoş comun':http://en.wikipedia.org/wiki/Lowest_common_ancestor al nodurilor $x$ şi $y$".

Se dă un 'arbore':http://en.wikipedia.org/wiki/Tree_%28graph_theory%29 cu rădăcină $T$. 'Cel mai apropiat strămoş comun':http://en.wikipedia.org/wiki/Lowest_common_ancestor a două noduri $u$ şi $v$ este nodul $w$ care este strămoş al ambelor noduri $u$ şi $v$ şi are cea mai mare adâncime în $T$.
 
Considerăm că arborele $T$ are $n$ noduri şi are rădăcina în nodul $1$. Dându-se o mulţime arbitrară $P = {{u,v}}$, cu $m$ perechi neordonate de noduri din $T$, se cere să se determine cel mai apropiat strămoş al fiecărei perechi din $P$.

h2. Date de intrare

Pe prima linie a fişierului de intrare $lca.in$ se găsesc $N$ şi $M$. Următoarea linie conţine $N - 1$ numere naturale, cel de-al $i$-lea număr reprezentând tatăl nodului $i + 1$ (nodul $1$ fiind rădăcină nu are tată). Pe următoarele $M$ linii se află câte $2$ numere naturale, reprezentând nodurilor care definesc întrebările.

Pe prima linie a fişierului de intrare $lca.in$ se găsesc $n$ şi $m$. Următoarea linie conţine $n-1$ numere naturale, cel de-al $i$-lea număr reprezentând tatăl nodului $i+1$ (nodul $1$ fiind rădăcină nu are tată). Pe următoarele $m$ linii se află câte o pereche de numere naturale, reprezentând elementele mulţimii $P$.

h2. Date de ieşire

Fişierul de ieşire $lca.out$ va conţine $M$ linii, linia $i$ conţinând răspunsul la întrebarea $i$.

Fişierul de ieşire $lca.out$ va conţine $m$ linii, linia a $i$-a conţinând răspunsul celei de a $i$-a întrebări.

h2. Restricţii