吵架

题目限制

4000 ms 256 M

题目描述

老虎和蒜头是好朋友，但他们经常吵架。吵完架之后，两人会各自去到一个僻静的角落，使得它们的距离最远。

他们所在的小镇有 $n$ 个角落，有 $n-1$ 条长度为 $1$ 的道路每条连接两个角落，角落互相可达；两个角落的距离等于它们之间简单路径的长度；起初所有的角落都是僻静的。

从 $1$ 到 $q$ 这 $q$ 天，每天会发生一个事件，用以下两者之一描述：

$C\ x$ ：角落 $x$ 的僻静性发生反转（原来僻静则现在吵闹，原来吵闹则现在僻静）

$G$ ：老虎和蒜头吵了一次架，你需要输出当它们各自去到想去的僻静角落之后它们之间的距离。这对角落应是所有僻静角落对中相距最远的一对。特别地，如果只有一个僻静的角落，输出 $0$ ；如果所有角落都吵闹，输出 $-1$

输入格式

第一行包含2个整数 n,q，分别表示角落的数量和天数。 接下来 n-1 行，每行两个整数 u,v，表示 u,v 通过道路直接相连。 接着 q 行，每行描述一天发生的事件，如上文所示。 其中 2≤n≤1e5，1≤q≤5e5。

输出格式

对于每个事件G，输出一行一个整数，表示相距最远的一对僻静角落之间的距离。特别地，如果只有一个僻静的角落，输出 0；如果所有角落都吵闹，输出 -1。

数据范围

对于 $20\%$ 的数据， $2\le n\le 100, 1\le q\le 100$ ；

对于 $60\%$ 的数据， $2\le n\le 5000, 1\le q\le 20000$ ；

对于 $100\%$ 的数据， $2\le n\le 10^5, 1\le q\le 5\times 10^5$

输入样例

8 7
1 2
2 3
3 4
3 5
3 6
6 7
6 8
G
C 1
G
C 2
G
C 1
G

输出样例

4
3
3
4