P11726 [JOIG 2025] 最悪の記者 5 / Worst Reporter 5

水獭乌苏太郎是一名报社记者，正在报道附近举行的一场大型马拉松比赛。

共有 $N$ 名运动员参加比赛，编号从 $1$ 到 $N$ 。乌苏太郎在报道比赛时，在笔记中记录了如下信息： - 比赛开始时，$N$ 名运动员位于不同的位置上； - 比赛过程中，排名变化恰好发生了 $M$ 次：在第 $i(1\le i\le M)$ 次排名变化中，运动员 $A_i$ 和 $B_i$ 交换位置，保证排名变化前两位运动员之间没有其他运动员； - 没有两个排名变化同时发生。 乌苏太郎想在报纸上刊登一张排名表，表示比赛结束后运动员的排名：排名表是一个长度为 $N$ 的序列 $P$，其中 $P_j$ 代表排名为 $j$ 的运动员的编号。 然而乌苏太郎并没有记录排名表，也没有记录每次排名变化时哪一方的排名上升（即不知道是 $A_i$ 超过了 $B_i$ 还是反之）。于是他想让你判断是否存在一个排名表，使得不与他记录的信息矛盾；如果存在，他想让你求出字典序最小的排名表。 称一个长度为 $N$ 的排名表序列 $a$ 在字典序上小于另一个长度为 $N$ 的排名表序列 $b$，当且仅当存在一个 $k(1\le k\le N)$ 满足如下条件： - $a_l=b_l(1\le l\le k-1)$； - $a_k

无

无

#### 【样例解释 #1】 假设比赛开始时，运动员排名为 $1,2,3,5,4$。 比赛过程如下： - 在第 $1$ 次排名变化中，运动员 $1,2$ 交换位置，排名变为 $2,1,3,5,4$； - 在第 $2$ 次排名变化中，运动员 $4,5$ 交换位置，排名变为 $2,1,3,4,5$； - 在第 $3$ 次排名变化中，运动员 $3,4$ 交换位置，排名变为 $2,1,4,3,5$； - 在第 $4$ 次排名变化中，运动员 $3,5$ 交换位置，排名变为 $2,1,4,5,3$； - 在第 $5$ 次排名变化中，运动员 $1,4$ 交换位置，排名变为 $2,4,1,5,3$； 最终的排名表 $P=\{2,4,1,5,3\}$。可以证明这是字典序最小的。 该样例满足子任务 $1,3,5$ 的限制。 #### 【样例解释 #2】 不存在与给定信息不矛盾的排名表。 该样例满足子任务 $1,3,5$ 的限制。 #### 【样例解释 #3】 该样例满足所有子任务的限制。 #### 【样例解释 #4】 该样例满足子任务 $1,3,4,5$ 的限制。 #### 【数据范围】 - $2\le N\le 5\times 10^5$； - $1\le M\le 5\times 10^5$； - $1\le A_i