P4299 Capital

On Planet X there are $n$ countries, each occupying exactly one city of Planet X. Cities are numbered from $1$ to $n$. Since countries are hostile to each other, there are no roads between cities of different countries. Wars often break out on Planet X. If country A defeats country B, then B disappears from the planet forever, and B’s territory comes under A’s control. To strengthen governance, the king of A will build a road between A and B: specifically, he chooses one original city of A and one city of B and builds a road connecting these two cities. To facilitate governing the country, the capital is chosen as the city that minimizes the sum of distances from all other cities in that country; here, distance means the number of roads traversed. If there are multiple such cities, the one with the smallest index becomes the capital. You are given the wars that happen on Planet X and need to process information about capitals. Specifically, there are three types of operations to handle: - `A x y`: Two countries go to war. The winner chooses cities $x$ and $y$ and builds a road between them (it is guaranteed that one of the two cities belongs to the winner and the other to the loser). - `Q x`: Query the current capital of the country containing city $x$. - `Xor`: Query the bitwise XOR of the indices of all current countries’ capitals.

The first line contains two integers, the number of cities $n$ and the number of operations $m$. Then follow $m$ lines. Each line starts with a string $op$ indicating the operation type, followed by several integers, with formats as described in the Description.

For each `Q` operation and `Xor` operation, output one line with a single integer as the answer.

Constraints For all testdata, it is guaranteed that $1 \leq n \leq 10^5$, $1 \leq m \leq 2 \times 10^5$, and $1 \leq x, y \leq n$. Translated by ChatGPT 5