The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Codeforces Round 151 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

data structures

dfs and similar

dp

sortings

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Blood Cousins Return

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPolycarpus got hold of a family tree. The found tree describes the family relations of *n* people, numbered from 1 to *n*. Every person in this tree has at most one direct ancestor. Also, each person in the tree has a name, the names are not necessarily unique.

We call the man with a number *a* a 1-ancestor of the man with a number *b*, if the man with a number *a* is a direct ancestor of the man with a number *b*.

We call the man with a number *a* a *k*-ancestor (*k* > 1) of the man with a number *b*, if the man with a number *b* has a 1-ancestor, and the man with a number *a* is a (*k* - 1)-ancestor of the 1-ancestor of the man with a number *b*.

In the tree the family ties do not form cycles. In other words there isn't a person who is his own direct or indirect ancestor (that is, who is an *x*-ancestor of himself, for some *x*, *x* > 0).

We call a man with a number *a* the *k*-son of the man with a number *b*, if the man with a number *b* is a *k*-ancestor of the man with a number *a*.

Polycarpus is very much interested in how many sons and which sons each person has. He took a piece of paper and wrote *m* pairs of numbers *v*_{i}, *k*_{i}. Help him to learn for each pair *v*_{i}, *k*_{i} the number of distinct names among all names of the *k*_{i}-sons of the man with number *v*_{i}.

Input

The first line of the input contains a single integer *n* (1 ≤ *n* ≤ 10^{5}) — the number of people in the tree. Next *n* lines contain the description of people in the tree. The *i*-th line contains space-separated string *s*_{i} and integer *r*_{i} (0 ≤ *r*_{i} ≤ *n*), where *s*_{i} is the name of the man with a number *i*, and *r*_{i} is either the number of the direct ancestor of the man with a number *i* or 0, if the man with a number *i* has no direct ancestor.

The next line contains a single integer *m* (1 ≤ *m* ≤ 10^{5}) — the number of Polycarpus's records. Next *m* lines contain space-separated pairs of integers. The *i*-th line contains integers *v*_{i}, *k*_{i} (1 ≤ *v*_{i}, *k*_{i} ≤ *n*).

It is guaranteed that the family relationships do not form cycles. The names of all people are non-empty strings, consisting of no more than 20 lowercase English letters.

Output

Print *m* whitespace-separated integers — the answers to Polycarpus's records. Print the answers to the records in the order, in which the records occur in the input.

Examples

Input

6

pasha 0

gerald 1

gerald 1

valera 2

igor 3

olesya 1

5

1 1

1 2

1 3

3 1

6 1

Output

2

2

0

1

0

Input

6

valera 0

valera 1

valera 1

gerald 0

valera 4

kolya 4

7

1 1

1 2

2 1

2 2

4 1

5 1

6 1

Output

1

0

0

0

2

0

0

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/02/2023 08:39:31 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|