Máte daný zakorenený strom a dvojice vrcholov. Pre každú z daných dvojíc zistite ich najnižšieho spoločného predka - teda taký vrchol, že oba vrcholy v dvojici patria do jeho podstromu, a žiadny z jeho synov už túto podmienku nespĺňa.
Prvý riadok obsahuje číslo $n$ ($1 \leq n \leq 10^5$), udávajúce počet vrcholov stromu. Druhý riadok obsahuje $n$ čísel, kde $i$-té číslo udáva otca vrcholu $i$. Vrcholy sú číslované od jednotky, koreň je vrchol číslo $1$ má uvedené ako otca číslo $0$. Tretí riadok obsahuje číslo $q$ ($1 \leq q \leq 3 \cdot 10^5$). Nasleduje $q$ riadkov obsahujúcich dvojice vrcholov.
Pre každú z $q$ dvojíc vrcholov vypíšte jeden riadok, obsahujúci číslo najnižšieho spoločného predka týchto dvoch vrcholov.
10
0 1 1 2 3 3 5 5 8 1
6
1 2
10 9
4 2
7 10
5 6
9 7
1
1
2
1
3
5