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
Let the current node that Theseus is at be
- 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,
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
Subtask 1 [10%]
Subtask 2 [20%]
Subtask 3 [70%]
It is guaranteed that node 1 will always be the root of the tree.
Input Specification
The first line of input will contain
The following
The next line will contain
The following 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:
Comments
HLD is too op 😫