[ZJOI2007]Hide 捉迷藏

Jiajia 和 Wind 是一对恩爱的夫妻，他们有许多孩子。一天，他们决定在家中玩捉迷藏。孩子们负责躲藏，Jiajia 负责寻找，而 Wind 负责控制房间里的灯。

他们的家由 $N$ 个房间和 $N-1$ 条双向走廊组成，任意两个房间之间都可以互相到达。初始时，所有房间的灯均处于关闭状态。孩子们只会躲在关灯的房间中，但为了增加游戏的刺激性，他们会要求 Wind 打开或关闭某个房间的灯。

为了评估游戏的复杂程度，Jiajia 希望知道当前距离最远的两个关灯房间之间的距离。

共有以下两种操作：

• C i：改变第 $i$ 个房间的照明状态。若该房间的灯原本打开，则将其关闭；若原本关闭，则将其打开。
• G：开始一次游戏，查询当前距离最远的两个关灯房间之间的距离。

输入格式

第一行包含一个整数 $N$，表示房间数量。房间编号为 $1,2,3,\ldots,N$。

接下来 $N-1$ 行，每行包含两个整数 $a,b$，表示房间 $a$ 与房间 $b$ 之间有一条双向走廊。

接下来一行包含一个整数 $Q$，表示操作次数。

随后 $Q$ 行，每行包含一个操作，格式如题目描述所示。

输出格式

对于每个 G 操作，输出一行一个整数，表示当前距离最远的两个关灯房间之间的距离。

若只有一个房间的灯处于关闭状态，则输出 $0$；若所有房间的灯均处于打开状态，则输出 $-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

数据范围

• 对于 $100\%$ 的数据，$N\le 10^5$；
• 对于 $100\%$ 的数据，$Q\le 5\times 10^5$。

来源与许可

本题为 ZJOI 2007 试题「Hide 捉迷藏」，题面与测试数据整理自 BZOJ。

样例 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