时空限制

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$ 的球开始，顺时针方向的最终排列。

样例

样例输入 #1

5 2
2 4
1 5

样例输出 #1

1 5 4 3 2

样例解释 #1

初始时，从位置 $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$。