[ZJOI2007] 捉迷藏

题目描述

Jiajia 和 Wind 是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind 和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由 $N$ 个屋子和 $N-1$ 条双向走廊组成，这 $N-1$ 条走廊的分布使得任意两个屋子都互相可达。

游戏是这样进行的，孩子们负责躲藏，Jiajia 负责找，而 Wind 负责操纵这 $N$ 个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，Jiajia 希望知道可能的最远的两个孩子的距离（即最远的两个关灯房间的距离）。

我们将以如下形式定义每一种操作：

• C(hange) i 改变第 $i$ 个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。
• G(ame) 开始一次游戏，查询最远的两个关灯房间的距离。

输入格式

第一行包含一个整数 $N$，表示房间的个数，房间将被编号为 $1,2,3…N$ 的整数。

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

接下来一行包含一个整数 $Q$，表示操作次数。接着 $Q$ 行，每行一个操作，如上文所示。

输出格式

对于每一个操作 Game，输出一个非负整数，表示最远的两个关灯房间的距离。若只有一个房间是关着灯的，输出 0；若所有房间的灯都开着，输出 -1。

样例 #1

样例输入 #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

样例输出 #1

4
3
3
4

提示

对于$20\%$的数据， $N \leq 50$, $M\leq 100$；

对于$60\%$的数据， $N \leq 3000$, $M \leq 10000$；

对于$100\%$的数据， $N \leq 100000$, $M \leq 500000$。