祖孙询问

题目描述

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

输入描述

输入第一行包括一个整数 n  表示节点个数；

接下来 n  行每行一对整数对 a  和 b  表示 a  和 b  之间有连边。如果 b  是 −1 ，那么 a  就是树的根；

第 n+2  行是一个整数 m  表示询问个数；

接下来 m  行，每行两个正整数 x  和 y ，表示一个询问。

数据范围与提示：

对于 30% 的数据，$1 \leq n,m \leq10^3 $；

对于 100% 的数据，$1 \leq n,m \leq 4 \times10^4 $，每个节点的编号都不超过$4 \times 10^4 $。

输出描述

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