#P3510. 首都
首都
首都
题目描述
X 星球上有 座城市,编号为 到 。最初每座城市单独组成一个国家,城市间没有公路。
战胜国吞并战败国时,在原来属于两个国家的两座城市间修建一条双向公路。原有公路继续保留。合并后,两国的城市都属于同一个国家。
两座城市间的距离是连接它们的路径所需的最少公路数。每个国家选一座城市为首都,使它到本国所有城市的距离之和最小。如果有多座这样的城市,选编号最小的。
依次处理以下操作。
A x y。在城市 和 间修建公路,并合并它们所在的国家。操作前二者属于不同国家。Q x。查询城市 所在国家当前的首都编号。Xor。查询当前所有国家的首都编号按位异或的结果。
输入格式
第一行有两个整数 ,分别表示城市数和操作数。接下来 行,每行描述一种操作,格式如上。
输出格式
每遇到 Q 或 Xor 操作,输出一行一个整数,表示该次查询的结果。
样例 #1
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
数据范围
,,。