A described relative

tree divide and conquer graph science and physics

A catalogue of languages is built as a forest: each family has a vertex, subgroups lie under it, and languages under them. Linguists publish grammars one after another, and each marks a vertex of the catalogue. Between publications colleagues ask: how far along the tree from a given vertex is the nearest marked one? The distance is the number of edges on the path along the tree; you cannot look in another family.

The third test is the Glottolog 5.3 tree of languages: 12,208 vertices; the marks are 1937 languages with a grammar over 300 pages, in random order, with questions about random languages between them.

Input

The first line holds n (1 ≤ n ≤ 5 · 10⁴). The second holds n numbers p₁, …, p_n: the parent of vertex v, or 0 if v is a family vertex. Then the number of messages q (1 ≤ q ≤ 5 · 10⁴) and q lines: 1 v, vertex v is marked (a repeated mark changes nothing), or 2 v, a question.

Output

For each question, the distance from v to the nearest marked vertex of its tree, 0 if v itself is marked, or -1 if its tree has no marked vertices.

Examples

Example 1

Input

7
0 1 1 2 2 3 3
7
2 4
1 7
2 4
2 6
1 5
2 4
2 1

Output

Example 2

Input

6
0 1 1 0 4 0
6
1 2
2 3
2 5
1 5
2 4
2 6

Output

2
-1
1
-1

Limits

Time · Python: 9500 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 9 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

One question is a breadth-first search from the vertex to the first mark. How much does it cost if there are few marks so far and they are all far away, as in the fourth test, where the only mark is at the end of a chain of 50,000 vertices? And there are tens of thousands of questions.

2Hint 2

Take a vertex whose removal leaves every part of the tree no larger than half. Any path from one part to another passes through it. What if you remember in it the distance to the nearest marked vertex, and do the same in each part?

3The idea

Centroid decomposition. Each vertex has at most log₂ n + 1 centroids above it, with a distance recorded for each. Each centroid c remembers best(c), the distance to the nearest marked vertex of its piece. Marking v lowers best at the centroids of v, and a question takes the smallest dist(v, c) + best(c). Why this is enough is proved in the article: the nearest marked vertex is counted at the first centroid taken on the path to it.

4Walkthrough

Build the pieces level by level, without recursion: for each piece, a traversal, subtree sizes, a descent into a part larger than half while there is one, and a breadth-first search from the centroid found, which appends to each vertex of the piece the pair “centroid, distance”. The centroid is removed, and its neighbours start pieces of the next level. In a forest the first-level pieces are the families. The pairs are conveniently kept in two parallel lists: this is faster in both Python and Go.

4+Solution

5Complexity

Preparation is O(n log n): on each level the traversals of the pieces together pass through each vertex at most once. A mark and a question are O(log n). Memory is O(n log n) pairs, in practice about five per vertex on the tree of languages.

6Common mistakes

A search from the question. This is wrong.py. The answers are right, but in the fourth test there is a single mark at the end of the chain, and the questions are about vertices of the other half: each one walks tens of thousands of vertices, and the time runs out.
A search from the marked vertices after each mark. Then questions are instant, but there are thousands of marks, and each costs O(n).
The centre instead of the centroid. The middle of the longest path splits the tree by length, not by number of vertices. For the broom in the sixth test the centre is the middle of the handle, and after removing it the bunch with half the handle, three quarters of the vertices, stays in one part: the bound of log₂ n levels is no longer guaranteed.
Recursion in the traversals and in the decomposition itself crashes on a chain of 50,000 vertices.

Algorithms behind it

GRA Algorithm Centroid decomposition Splitting a tree by centroids: log₂ n levels, and the nearest marked vertex in O(log n) after every mark. O(log n) per mark and per question 1 problem GRA Algorithm Breadth-first search Walks a graph in layers and finds paths with the fewest edges in O(V + E). O(V + E) 2 problems