One of the most famous quotes from the cartoon: "Ohana — it means family, in the family they will not leave anyone and they will never forget…» What else is there to add? So it is!
Lilo wants to make a family tree of her family in order to try to find as many of her relatives as possible. In the family tree, as you know, everyone except the ancestor has exactly one parent. Lilo wants to know how to position some two family members in relation to each other. Lilo's older sister Nani remembers perfectly who is the parent of whom. She is ready to help Lilo, but she has so much work to do. Help Nani write a program for Lilo.
Input
The program receives as input the number of elements in the genealogical tree N. This is followed by a \(N-1\) string that specifies the parent for each element in the tree, except for the ancestor. Each line looks like:
child_name parent_name.
Further to the end of the file there are lines containing the names of two elements of the tree.
Imprint
For each such query, print one of three numbers:
1 - if the first element is an ancestor of the second;
2 - if the second is an ancestor of the first;
0 - if neither is an ancestor of the other.
Examples
| # |
Input |
Output |
| 1 |
9
Keaka Kayla
Ikika Kayla
Akeneki Kayla
Neolani Keaka
Ley Ikika
Kianalu Ley
Aalona Kianalu
Iukini Kianalu
Ikika Iukini
Neolani Kayla
Keaka Kianalu
END!
|
1 2 0
|