#P2056. [ZJOI2007] 捉迷藏

[ZJOI2007] 捉迷藏

题目描述

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

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

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

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

输入格式

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

接下来 N1N-1 行每行两个整数 aa, bb,表示房间 aa 与房间 bb 之间有一条走廊相连。

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

输出格式

对于每一个操作 Game,输出一个非负整数,表示最远的两个关灯房间的距离。若只有一个房间是关着灯的,输出 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%20\%的数据, N50N \leq 50, M100M\leq 100

对于60%60\%的数据, N3000N \leq 3000, M10000M \leq 10000

对于100%100\%的数据, N100000N \leq 100000, M500000M \leq 500000