Description

In the programming academy, students enjoy learning from each other, where each person can become the “seafu” of others. Over time, this has led to a unique hierarchical system similar to a tree structure.

Within the academy, every student has exactly one "direct seafu,” except for the "Master LJH”, who sits atop the academy's hierarchy. He is the only one without a "direct seafu”, and he is the “seafu” of every students.

There are N students in the academy, each person has a uniuqe id number from 1 ~ N. There is a unique custom in the academy, seafu's id must be smaller than disciples' id. So "LJH" is always id number 1.

Now give you every student's direct seafu's id (except “LJH”), please answer the following questions.

Note: a student can be more than 1 students' "direct seafu", but can only have 1 "direct seafu".

Distance Calculation:

Calculate the distance between the "Master LJH" and every other person in the academy. The distance between a person and master "LJH" is the number k which a person's k level seafu is "LJH".

Level Seafu Query:

Respond to Q queries, each of the form (A, B), where A represents a person and B represents a level. For each query, determine person A's B level seafu. If such a seafu does not exist, print -1.

What is K level seafu? direct seafu is 1 level seafu, direct seafu's direct seafu is 2 level seafu, and so on...

Input

• The first line contains an integer N (1 ≤ N ≤ 1000), representing the number of people (excluding LJH) in the academy.
• The second line contains N - 1 space-separated integers, representing p_2, p₃, ..., p_N, which p_i means the direct seafu id of student i.
• Student id number 1 is always master LJH. And it is guarantee that p_i < i.
• The following line contains an integer Q (1 ≤ Q ≤ 1000), representing the number of queries.
• Each of the next Q lines contains two integers A and B, representing a query.

Output

• The first line outputs N - 1 integers, representing the distance between person 2 to N and master “LJH”. (No space in the end)
• In the next Q lines, output the answer to each query in sequence.

Sample Input  Download

Sample Output  Download

Tags

Discuss