bzoj#P3510. 首都
首都
题目描述
在 X 星球上有 个国家,每个国家占据着 X 星球的一座城市。由于国家之间是敌对关系,所以不同国家的两个城市是不会有公路相连的。
X 星球上战乱频发,如果 A 国打败了 B 国,那么 B 国将永远从这个星球消失,而 B 国的国土也将归 A 国管辖。A 国国王为了加强统治,会在 A 国和 B 国之间修建一条公路,即选择原 A 国的某个城市和 B 国某个城市,修建一条连接这两座城市的公路。
同样为了便于统治自己的国家,国家的首都会选在某个使得其他城市到它距离之和最小的城市,这里的距离是 指需要经过公路的条数,如果有多个这样的城市,编号最小的将成为首都。 现在告诉你发生在 X 星球的战事,需要你处理一些关于国家首都的信息,具体地,有如下 种信息需要处理:
A x y
:表示某两个国家发生战乱,战胜国选择了 城市和 城市,在它们之间修建公路(保证其中城市一个在战胜国另一个在战败国)。Q x
:询问当前编号为 的城市所在国家的首都。Xor
:询问当前所有国家首都编号的异或和。
输入格式
第一行是整数 ,表示城市数和需要处理的信息数。
接下来每行是一个信息,格式如题目描述(A
、Q
、Xor
中的某一种)。
输出格式
输出包含若干行,为处理 Q
和 Xor
信息的结果。
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
提示
对于 的数据,,。