400404: GYM100162 K Ant versus Woodpecker

The Ant lives near a tree, or, to be precise, near the tree root. The tree consists of n nodes and n - 1 branches, each branch connects a pair of nodes. The Ant can reach any node walking only along tree branches. The tree nodes are numbered from 1 to n, and the root is the node number one.

From time to time the Ant does a sally for obtaining a food. Before doing each sally, the Ant finds out v₁, v₂, ..., v_k — numbers of nodes containing the food. The Ant wants to visit all these nodes. He starts his way in the tree root, then, moving along the tree branches, visits all nodes with food in arbitrary order, and finally returns back to the tree root.

The Ant's life is not easy, as he is always in danger: the Woodpecker hunts him! Namely, if the Ant visits some node more than two times on his way, then he risks being noticed by the Woodpecker. If the Ant is noticed by the Woodpecker, then he starts running away. In that case the Ant interrupts his sally and returns to the root using the shortest path. The longer is the distance from the root to the node where he was noticed, the worse is the situation. That's why the Ant wants to find such path visiting all nodes with food which will minimize this escape distance in the worst case.

Write a program that will determine the maximum distance from the root to the node where the Ant can be noticed by the Woodpecker if the Ant chooses the optimal path. You will be given descriptions of several sallies, and you will have to find the optimum value for each of them.

Additionally, the tree is not static:

• new nodes may be added to the tree (i.e. a node and a branch connecting it to one of the existing nodes are created),
• nodes can be deleted (i.e. some branch breaks off, and a whole subtree disappears).

The input consists of one or more test cases.

Each test case starts with a line containing integer n (2 ≤ n ≤ 10⁵) — the number of nodes in the tree in the beginning. The second line contains the initial tree description: n - 1 integers p₂, ..., p_n, where p_i (i = 2... n) is the number of node from which the Ant will go to the i-th node if he moves away from the root. It is guaranteed that the input describes a correct tree with nodes numbered from 1 to n.

Then an integer m follows — the number of queries (1 ≤ m ≤ 10⁵). Each query describes one of the three events: the Ant's sally, creation of a node, or deletion of a subtree. Each of the following m lines describes a query using one of the following formats:

• Query of the first kind: "".

  The Ant has to visit k nodes with food with given distinct numbers v₁, v₂, ..., v_k (the Ant may vary the order of visiting these nodes). As an answer for this query you have to output the longest escape distance for the Ant if he chooses the optimal path (or output  - 1 if the Ant may finish his path without a risk of being captured by the Woodpecker).

  It is guaranteed that the nodes numbered v₁, v₂, ..., v_k existed just before executing this query.

• Query of the second kind: «».

  A new node, connected with one of the existing nodes, appears in the tree. The new node gets numbered as the smallest positive integer not occupied currently by any other node. This new node gets connected with a branch to the existing node number x + y, where number y is the result of the last query of the first kind. It is guaranteed that at least one query of the first kind has already occurred, and that the node number x + y existed just before executing this query. The number x in the input may be an arbitrary integer satisfying restrictions above.

• Query of the third kind: «».

  The node number v with its subtree has to be deleted from the tree. A subtree is a set of nodes which can't be reached from the root without visiting node v. Pay attention to that the numbers of deleted nodes are being freed, i.e. these numbers become available for the new nodes in subsequent queries of the second kind. It is guaranteed that the node number v existed just before executing this query. Also it is guaranteed that v > 1, i.e. the tree root cannot be deleted.

Sum of k over all queries of the first kind in one test case does not exceed 10⁵.

For each test case, output a line containing the test number and the answers for all queries of the first kind. It is guaranteed that each test case contains at least one query of the first kind. The queries should be processed in the order they are given in the input.

3
1 1
4
? 2 2 3
+ 2
+ 2
? 3 2 4 5
2
1
4
? 2 1 2
? 1 2
- 2
? 1 1
5
3 1 1 3
4
? 2 2 5
- 2
+ 0
? 2 2 5

Case 1: 0 1
Case 2: -1 -1 -1
Case 3: 1 0