View as PDF

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

The Labyrinth was said to be an ever-shifting, inescapable maze — Daedalus's most cunning creation. Those who were unfortunate enough to find themselves in it were destined to be trapped for the rest of their lives — which were usually quite short. Our hero Theseus was sent on a seemingly impossible quest to slay the Minotaur, a monster that lurked in the depths of the Labyrinth. Fortunately, his beloved, Ariadne, was just as smart as Daedalus.

Ariadne had managed to sneak a peek at the blueprints for the Labyrinth and noticed that it was actually in the form of a rooted tree consisting of nodes, numbered through . To prevent the rather dim Theseus from getting himself lost, she gave him a ball of thread as well as specific instructions on how to explore the maze.

Let the current node that Theseus is at be . Then:

• Theseus should move to the leftmost unvisited child of
• If all of 's children have been visited or if is a leaf, Theseus should backtrack and return to 's parent

But Ariadne is still anxious. So she decided to ask you, her trusty adviser, queries of the following form:

Suppose that Theseus enters the Labyrinth at node and the Minotaur is located at node , how many edges will Theseus pass before reaching the Minotaur if he follows Ariadne's instructions perfectly?

#### Constraints

,

,

,

It is guaranteed that node 1 will always be the root of the tree.

#### Input Specification

The first line of input will contain , the number of nodes in the tree.

The following lines will describe the tree. The of these lines begin with an integer , denoting the number of children of node , followed by space-separated integers, the labels of its children from left to right.

The next line will contain , the number of queries.

The following lines will each contain a query in the form u v.

#### Output Specification

Output the answer to each query on a separate line.

#### Sample Input

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

#### Sample Output

5
8
1

#### Explanation for Sample Output

The Labyrinth looks like this:

In the first query, Theseus will walk the following path: .

In the second query: .

In the third query: .