[R31C]交换小球 - 代码源竞赛平台

时空限制

1S/512M

有 $n$ 个球排成一个圆环。从一个固定的“位置 $1$ ”开始，顺时针方向的第 $i$ 个位置上放着一个写有整数 $i$ 的球（ $i=1, 2, \ldots, n$ ）。

接下来将进行 $Q$ 次操作。第 $i$ 次操作会给出两个整数 $a_i$ 和 $b_i$ ，你需要找到写有这两个整数的球，然后交换它们所在的位置。

在所有 $Q$ 次操作结束后，请输出球的最终排列。输出要求为：首先找到写有整数 $1$ 的球，然后从该球开始，按顺时针方向依次输出圆环上所有球上写的整数。

输入的第一行包含两个整数 $n$ 和 $Q$ ，分别表示球的数量和操作的次数。

接下来 $Q$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ，表示一次交换操作。

输出一行，包含 $n$ 个用空格分隔的整数，表示从写有整数 $1$ 的球开始，顺时针方向的最终排列。

5 2
2 4
1 5

1 5 4 3 2

初始时，从位置 $1$ 开始顺时针方向的球的排列为： $[1, 2, 3, 4, 5]$ 。

第 $1$ 次操作，交换写有数字 $2$ 和 $4$ 的球，此时从位置 $1$ 开始的排列变为： $[1 ,4, 3, 2, 5]$ 。

第 $2$ 次操作，交换写有数字 $1$ 和 $5$ 的球，此时从位置 $1$ 开始的排列变为： $[5 ,4 ,3 ,2, 1]$ 。

所有操作结束后，找到写有数字 $1$ 的球，它现在位于原来的第 $5$ 个位置上。从这个球开始顺时针读取一圈，得到的序列是 $[1,5,4,3,2]$ 。

对于 $30\%$ 的数据， $2 \leq n,Q \leq 2000$ 。

对于 $100\%$ 的数据， $2 \leq n \leq 10^5$ ， $1 \leq Q \leq 10^5$ ， $1 \leq a_i, b_i \leq n$ ，且 $a_i \neq b_i$ 。