CF246E Blood Cousins Return

Polycarpus 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 \gt 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 \gt 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} $ .

The first line of the input contains a single integer $ n $ $ (1 \le n \le 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 \le r_{i} \le 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 \le m \le 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 \le v_{i},k_{i} \le 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.

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.