Jiajia and Wind's Hide and Seek

Jiajia and Wind are a loving couple with many children. One day, they decided to play a game of hide and seek at home. Their house has a peculiar design consisting of \(N\) rooms and \(N-1\) bidirectional corridors, arranged so that any two rooms are reachable.

The game rules are as follows: The children hide in rooms where the light is turned off, while Jiajia is the seeker and Wind controls the lights in the \(N\) rooms. Initially, all the lights are off. In each move, the children will only hide in rooms that are off; however, to increase the excitement, they may request to toggle (turn on if off or off if on) the light in a specified room.

We define two types of operations:

• C i: Toggle the light in room \(i\). If the light was on, it becomes off, and vice versa.
• G: Start a game and query the distance between the two furthest rooms (i.e. among those with the light off) where the children can hide.

The distance between two rooms is defined as the number of corridors on the unique path between them. If there are fewer than 2 rooms with the light off, output 0 for the query.

Your task is to process \(Q\) operations on the house. Each operation is either a toggle operation or a query:

Input Format:
  The first line contains an integer \(N\) representing the number of rooms.
  The next \(N-1\) lines each contain two integers \(u\) and \(v\), indicating there is a corridor between room \(u\) and room \(v\).
  The next line contains an integer \(Q\), the number of operations.
  The following \(Q\) lines each contain an operation in one of the following formats:
    - "C i" (toggle the light in room \(i\))
    - "G" (query the maximum distance between two off-light rooms)
    

Output Format:

For each "G" operation, output a single integer on a new line, which is the maximum distance between any two rooms that have the light off. If fewer than 2 rooms are off, output 0.
    

inputFormat

The input begins with an integer \(N\) (the number of rooms). The next \(N-1\) lines each contain two integers \(u\) and \(v\) denoting a corridor connecting room \(u\) and room \(v\). Following that, an integer \(Q\) is provided, representing the number of operations. The next \(Q\) lines each contain an operation:

• C i: Toggle the light in room \(i\).
• G: Query the largest distance between any two rooms with the light off.

outputFormat

For every "G" operation encountered in the input, output a single integer on a new line representing the maximum distance between any two rooms that currently have the light off. If there are fewer than 2 off-light rooms, output 0.

sample

3
1 2
2 3
3
G
C 2
G

2
2

</p>