最近公共祖先(LCA)
時間限制(普通/Java):2000MS/20000MS          運行內存限制:65536KByte
總提交:248            測試通過:75

描述


給定一棵有根樹，詢問數上某兩個節點的公共祖先中離根最遠的一個的編號

例如：

1

/    \ 

2       3

/  \     /  \

4   5   6   7

/  \

8          9

若詢問節點4 和9 ，則回答2


輸入


第一行一個數n 表示樹的節點數

接下來n行每行一個數fi  第i+1行的數表示i節點的父節點編號

父節點編號為0的節點為根

第n+2行一個數m 表示問題數 

接下來m行 每行兩個數xi yi 詢問xi yi的公共祖先中離根最遠的一個的編號

n+m<=100000


輸出


M行

按輸入順序給出詢問的回答

 


樣例輸入

9
0
1
1
2
2
3
3
5
5
1
4 9


樣例輸出

2

提示

Huge input, scanf is recommended

題目來源

Saint Pajamas