描述

lxhgww 在树上玩耍时，LZX2019 走了过来。lxhgww 突然问道：“我现在的k级祖先是谁？”
LZX2019 答道：“不是我吗？”。接着 lxhgww 就用教主之力让 LZX2019 消失了，现在他转过头准备向你求助。

格式

输入格式

第一行包含一个整数N，表示树的结点数。

接下来N-1行包含两个整数X,Y,表示第X个结点和第Y个结点间有一条边。

接下来1行包含一个整数M,表示询问个数。

接下来M行包含两个整数a,b,则x=a^lastans,k=b^lastans。

输出格式

输出包含M行，分别是M个询问的答案。
若没有k级祖先,则输出0

样例

样例输入

5
1 2 
2 3 
1 4 
4 5 
5
5 0
6 7
4 5
2 1
4 3

样例输出

5
1
0
1
1

限制

每个测试点1s,512MB

提示

数据范围：
1 ≤ N ≤300000, M ≤ 1800000
1 ≤ x,k≤ N

Source

LZX2019