5
1 4 5 3 2
1 2
2 4
2 3
4 5

1
2
1
2
1

2<= n <=300000

# RCC 16 3rd qualification round D Tree（线段树+LCA）

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.

Input format 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.

Output format For each query of type 2 print the distance between the corresponding vertices, one per line.
Examples

Input data

Output data

# BZOJ 1832: [AHOI2008]聚会&1787: [Ahoi2008]Meet 紧急集合（求树上三点距离和最小）

## Description

Y岛风景美丽宜人，气候温和，物产丰富。Y岛上有N个城市，有N-1条城市间的道路连接着它们。每一条道路都连接某两个城市。幸运的是，小可可通过这些道路可以走遍Y岛的所有城市。神奇的是，乘车经过每条道路所需要的费用都是一样的。小可可，小卡卡和小YY经常想聚会，每次聚会，他们都会选择一个城市，使得3个人到达这个城市的总费用最小。 由于他们计划中还会有很多次聚会，每次都选择一个地点是很烦人的事情，所以他们决定把这件事情交给你来完成。他们会提供给你地图以及若干次聚会前他们所处的位置，希望你为他们的每一次聚会选择一个合适的地点。

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

## Sample Output

5 2
2 5
4 1
6 0

100%的数据中，N<=500000，M<=500000。
40%的数据中N<=2000，M<=2000。

update：发现和1787是一个题。。。