beecrowd | 3314

Konfused, the Hive!

By Thiago Lima Oliveira, USP BR Brazil

Timelimit: 1

In the city of Nlogonia there is only one hive, and as in every hive there is only one queen. In this hive all bees have a single direct ancestor. Besides, everyone is the queen's child directly or indirectly.

All bees can be identified by a number and a name, and both are unique to each bee. The queen bee for example is bee number 1, and its name is the empty string. To give the number of a bee, the system is very simple, every time a new bee is born, it receives the smallest number that has not yet been used. However, bees have a peculiar naming system for their descendants. Whenever a bee has a child, its child's name is its own name concatenated with some lowercase letter. So, if a bee has a name ’aa’, the possible names for its offspring are: ’aaa’, ’aab’, ..., ’aaz’.

Now the queen bee has a list with the names of all N bees (including her own) in alphabetical order, and wants to know the answer to Q questions like: given the i and j positions in my list, how big is the biggest prefix in common between the name in position i and the name in position j.

Knowing the importance of bees to the ecosystem, you want to help answer all the queen bee's questions.

NOTE: The name of the bees in the first test case in alphabetical order is (∅, a, aa, ab, c). Therefore, between the third and fourth name we have the prefix ’a’ in common, and between the second and fifth we have no prefix in common.


The first line of input contains two integers N and Q (1 ≤ N, Q ≤ 100000), the number of bees in the hive, and the number of questions the queen bee wants to ask. The next N – 1 lines contain an integer p and a lowercase letter c separated by white space. The i-th of these lines represents that the ancestor of the bee i + 1 is p, and that the name of the bee i + 1 is the name of the bee p concatenated with the character c. The next Q lines contain two integers separated by a space, representing a question from the queen bee. The queen bee will always have an empty name and will be identified by the number 1.


The output should contain Q lines, each of them containing an integer where the i-th line should contain the answer to the i-th question of the queen.

Input Samples Output Samples

5 2

1 a

2 a

2 b

1 c

3 4

2 5



4 3

1 z

2 z

1 y

1 2

3 4

4 2