bzoj#P3510. 首都

首都

题目描述

在 X 星球上有 nn 个国家,每个国家占据着 X 星球的一座城市。由于国家之间是敌对关系,所以不同国家的两个城市是不会有公路相连的。

X 星球上战乱频发,如果 A 国打败了 B 国,那么 B 国将永远从这个星球消失,而 B 国的国土也将归 A 国管辖。A 国国王为了加强统治,会在 A 国和 B 国之间修建一条公路,即选择原 A 国的某个城市和 B 国某个城市,修建一条连接这两座城市的公路。

同样为了便于统治自己的国家,国家的首都会选在某个使得其他城市到它距离之和最小的城市,这里的距离是 指需要经过公路的条数,如果有多个这样的城市,编号最小的将成为首都。 现在告诉你发生在 X 星球的战事,需要你处理一些关于国家首都的信息,具体地,有如下 33 种信息需要处理:

  1. A x y:表示某两个国家发生战乱,战胜国选择了 xx 城市和 yy 城市,在它们之间修建公路(保证其中城市一个在战胜国另一个在战败国)。
  2. Q x:询问当前编号为 xx 的城市所在国家的首都。
  3. Xor:询问当前所有国家首都编号的异或和。

输入格式

第一行是整数 n,mn,m,表示城市数和需要处理的信息数。

接下来每行是一个信息,格式如题目描述(AQXor 中的某一种)。

输出格式

输出包含若干行,为处理 QXor 信息的结果。

10 10
Xor
Q 1
A 10 1
A 1 4
Q 4
Q 10
A 7 6
Xor
Q 7
Xor
11
1
1
1
2
6
2

提示

对于 100%100\% 的数据,2n1052 \le n \le 10^51m2×1051 \le m \le 2 \times 10^5