View as PDF

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem types

In this problem, you will be required to support the following operations on a forest:

1 u v - Make node the parent of if is a root, and is not in the subtree of .

2 u v - Delete the edge between nodes and if it exists.

3 u v - Print the highest common ancestor of nodes and . If no such node exists, print -1.

There will be operations of this form.

However, at most two out of the three operations will appear in any given test case.

#### Input Specification

The first line will contain one integer .

The next lines will contain integers , the parent of node .

Nodes with parent are roots.

The next line will contain one integer .

The next lines will contain one query described above.

#### Output Specification

The answers to the queries, each on one line in the order of the queries.

#### Sample Input

3
0 0 1
5
3 1 1
3 1 2
3 1 3
1 1 2
3 1 2

#### Sample Output

1
-1
1
1