提示: 欢迎访问OurACM平台。
Problem 1628 Count Common Ancestors

Accept: 150    Submit: 620
Time Limit: 2000 mSec    Memory Limit : 32768 KB

Problem Description

This problem is very simple and well known.

It is shown as follows:

There is a tree which has n nodes, and the nodes are numbered from 1 to n, No. 1 is always the root of the tree. Given you two nodes of the tree, you should count the total number of their common ancestors.

Input

There are mulitiple tests. For each test, the first line is an integer n(1<=n<=50000), following n lines, the i+1-th line denotes the information of the i-th node. For each line, there is an integer k(0<=k<=n-1), denoting the number of direct children of the i-th node. Then following k integers, denoting the No. of the i-th node. When k is equal to 0, denoting the i-th node is leaf node. You should note that the node can be the ancestor of itself.

The n+2-th line is an integer m (1<=m<=30,000), denoting there are m queries. Following m lines, for each line, there are two integers x and y, denoting the No. of the two nodes.

Output

For each query, you should count the total number of their common ancestors.

Sample Input

12 3 2 3 4 2 5 6 0 0 2 7 8 2 9 10 0 0 0 2 11 12 0 0 6 3 11 7 12 4 8 9 12 8 10 1 12

Sample Output

1 2 1 3 2 1

Source

Summer Training Qualification II

Submit  Back  Status  Discuss