捉迷藏

题目描述:

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，输出一个非负整数到hide.out，表示最远的两个关灯房间的距离。若只有一个房间是关着灯的，输出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

提示:

对于20%的数据，   N ≤50, M ≤100；

对于60%的数据，   N ≤3000, M ≤10000；

对于100%的数据， N ≤100000, M ≤500000。

时间限制: 5000ms
空间限制: 256MB

---

来源: 浙江省选2007day2t3