给定一棵二叉树,多次给出这棵树上的两个节点 o1 和 o2,请对于每次询问,找到 o1 和 o2 的最近公共祖先节点。
输入描述:
第一行输入两个整数 n 和 root,n 表示二叉树的总节点个数,root 表示二叉树的根节点。以下 n 行每行三个整数 fa,lch,rch,表示 fa 的左儿子为 lch,右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子,rch同理)第 n+2 行输入一个整数 m,表示询问的次数。以下 m 行每行两个节点 o1 和 o2。


输出描述:
对于每组询问每行输出一个整数表示答案。
示例1

输入

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

输出

2
2
3
1
加载中...