Description

Jiajia and Wind are a loving couple, and they have many children. One day, Jiajia, Wind, and the children decide to play hide-and-seek at home. Their house is large and unusual: it consists of $N$ rooms and $N-1$ bidirectional corridors whose layout ensures that any two rooms are mutually reachable.

The game proceeds as follows: the children hide, Jiajia searches, and Wind controls the lights in the $N$ rooms. Initially, all lights are off. Each time, the children will only hide in rooms whose lights are off. To make the game more exciting, the children may request to turn on or turn off the light of a certain room. To evaluate the complexity of a particular round, Jiajia wants to know the greatest possible distance between two children, that is, the maximum distance between two rooms whose lights are off.

Each operation is defined as follows:

• C(hange) i: Toggle the light state of room $i$. If it was on, turn it off; if it was off, turn it on.
• G(ame): Start a round and query the maximum distance between two rooms with lights off.

Input Format

The first line contains an integer $N$, the number of rooms. The rooms are labeled with integers $1, 2, 3, \ldots, N$.

Each of the next $N-1$ lines contains two integers $a$, $b$, indicating that there is a corridor between room $a$ and room $b$.

The next line contains an integer $Q$, the number of operations. Then follow $Q$ lines, each containing one operation as described above.

Output Format

For each Game operation, output a non-negative integer representing the maximum distance between two rooms whose lights are off. If there is only one room with its light off, output 0. If all rooms have their lights on, output -1.

8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
7
G
C 1
G
C 2
G
C 1
G

4
3
3
4

Hint

Constraints

• For $20\%$ of the testdata, $N \leq 50$, $Q \leq 100$.
• For $60\%$ of the testdata, $N \leq 3000$, $Q \leq 10000$.
• For $100\%$ of the testdata, $N \leq 100000$, $Q \leq 500000$.

Translated by ChatGPT 5