|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|2 초||512 MB||3||3||3||100.000%|
Nick has got a rooted tree with n vertices as his birthday present.
Recall that a rooted tree is a connected undirected graph, one vertex is chosen as a root. For each vertex the closest to the root neighbor is called the parent of this vertex, other neighbors are its children. The root has no parent. Nick's tree has vertices numbered from 1 to n, vertex with number 1 is the tree root.
Nick has decided to play with his tree. He chooses some vertex u and removes it, connecting the vertices that were its children to the former parent vertex of u. The root is never removed. But it is not interesting to just remove the vertices, so sometimes he asks for the length of the path from one vertex to another in the current tree. Answer to Nick's questions.
The first line of the input contains integer n (1 ≤ n ≤ 100 000) — the number of vertices in the initial tree. The second line contains n - 1 integers pi (1 ≤ pi ≤ n) — parents of vertices 2, 3, ..., n.
The third line contains integer q (1 ≤ q ≤ 100 000) — the number of queries. Each of the following q lines contains queries. Each query starts with a query type — an integer equal either to 1 or to 2. If the query type is 1, it is followed by a and b (1 ≤ a, b ≤ n) — the numbers of vertices the distance between which must be found. If the query type is 2, one integer v (1 ≤ v ≤ n) follows — the number of the vertex to remove.
It is guaranteed that the initial tree is given correctly, the vertices in queries are not removed yet, and the root is never removed.
For each query of type 2 print the distance between the corresponding vertices, one per line.
8 1 5 2 1 2 5 5 7 2 4 1 7 6 2 5 1 3 8 1 8 6 2 2 1 8 6
4 2 3 2