Середина пути

Для каждого запроса $(u, v)$ выведите вершину, стоящую посередине пути: на расстоянии $\lfloor d/2 \rfloor$ от $u$, где $d$ — длина пути.

В первой строке $n$ ($1 \le n \le 2 \cdot 10^5$), во второй — $n-1$ родителей. Далее $q$ ($1 \le q \le 2 \cdot 10^5$) и $q$ пар вершин.

Для каждого запроса выведите номер вершины-середины.