题目描述

已知一棵 n 个节点的有根树。有 m 个询问，每个询问给出了一对节点的编号 x 和 y，询问 x 与 y 的祖孙关系。

输入格式

输入第一行包括一个整数 n 表示节点个数； 接下来 n 行每行一对整数对 a 和 b 表示 a 和 b 之间有连边。如果 b 是 -1，那么 a 就是树的根； 第 n+2 行是一个整数 m 表示询问个数； 接下来 m 行，每行两个正整数 x 和 y，表示一个询问。

输出格式

对于每一个询问，若 x 是 y 的祖先则输出 1，若 y 是 x 的祖先则输出 2，否则输出 0。

样例

输入样例 1

10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19

输出样例 1

1
0
0
0
2

输入样例 2

10
5 2
2 1
3 2
4 2
6 3
7 3
8 4
9 4
10 6
1 -1
10
1 2
2 1
3 7
7 3
4 8
8 4
5 10
10 5
9 10
10 9

输出样例 2

1
2
1
2
1
2
0
0
0
0

输入样例 3

20
2 1
3 1
4 2
5 2
6 3
7 3
8 4
9 4
10 5
11 5
12 6
13 6
14 7
15 7
16 8
17 8
18 9
19 9
20 10
1 -1
15
1 15
15 1
2 11
11 2
3 14
14 3
4 17
17 4
5 20
20 5
6 13
13 6
7 15
8 16
9 19

输出样例 3

1
2
1
2
1
2
1
2
1
2
1
2
1
1
1

提示

数据范围：1<=n,m<= 410^4，节点的编号都大于0但不超过 410^4。

思路：基于DFS序的时间戳进行父子节点的关系判断。 如果 in[u] < in[v] 且 out[u] >= out[v]，那么节点 u 是节点 v 的祖先。 生成 DFS 序 O(n)。基于时间戳的单次查询 O(1)，m次查询 O(m)。