Jiajia and Wind are a loving couple with many children. One day, Jiajia, Wind, and their children decide to play hide-and-seek at home. Their house is large and has a peculiar structure, consisting of $N$ rooms and $N-1$ bidirectional corridors, such that any two rooms are reachable from each other.

The game proceeds as follows: the children are responsible for hiding, Jiajia is responsible for searching, and Wind is responsible for operating the lights in these $N$ rooms. Initially, all lights are off. Each time, the children only hide in rooms where the light is off. To make it more exciting, the children will ask to turn the light on or off in a specific room. To evaluate the complexity of a game, Jiajia wants to know the maximum distance between any two children (i.e., the distance between the two farthest rooms with lights off).

We define each operation as follows:

Input

The first line contains an integer $N$, representing the number of rooms, which are numbered $1, 2, 3, \dots, N$. The next $N-1$ lines each contain two integers $a$ and $b$, indicating a corridor between room $a$ and room $b$. The next line contains an integer $Q$, representing the number of operations. The following $Q$ lines each contain an operation as described above.

Output

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

Examples

Input 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

Output 1

4
3
3
4

Constraints

For 20% of the data: $N \le 50, Q \le 100$; For 60% of the data: $N \le 3000, Q \le 10000$; For 100% of the data: $N \le 100000, Q \le 500000$.