AT_joig2025_d 最悪の記者 5 (Worst Reporter 5)

水獭"ウソ太郎"是一名新闻记者，正在采访附近即将举行的大型马拉松比赛。 本次比赛共有 $N$ 名选手参赛，选手们编号为 $1$ 到 $N$。ウソ太郎在采访过程中将以下信息记录在了笔记中： - 在比赛开始时，$N$ 名选手各自拥有 $1$ 到 $N$ 中某一名次，且这些名次互不相同。 - 排名变化共发生了恰好 $M$ 次。在第 $i$ 次（$1 \leq i \leq M$）排名变化时，选手 $A_i$ 和选手 $B_i$ 的名次发生了交换。在每一次排名变化中，发生交换的两位选手的排名差的绝对值均为 $1$。 - 不会有多次排名变化同时发生。 ウソ太郎想在报纸上刊登每位选手最终名次的“排名表”。所谓排名表，是一个长度为 $N$ 的序列，其中第 $j$ 项（$1 \leq j \leq N$）表示最终获得第 $j$ 名的选手编号。 但是ウソ太郎不仅没有记录下排名表，甚至都没有记录每次变动中到底是谁上升了名次。因此，ウソ太郎决定，从所有与笔记内容不矛盾的排名表中，选择字典序最小的一个进行报道。 对于两个长度为 $N$ 的序列 $(a_1, a_2, \dots, a_N)$ 和 $(b_1, b_2, \dots, b_N)$，称第一个序列“字典序更小”，当且仅当存在某个整数 $k$（$1 \leq k \leq N$），同时满足： - 对于所有整数 $l$（$1 \leq l \leq k-1$），有 $a_l = b_l$； - $a_k < b_k$。 现已给出选手人数 $N$ 及笔记中记录的每次名次变动的信息，请判断是否存在与笔记内容不矛盾的排名表，并在存在时输出字典序最小的有效排名表。

输入为如下格式： > $N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ > $\vdots$ > $A_M$ $B_M$

若不存在与笔记内容不矛盾的排名表，则输出一行 `No`。 若存在符合要求的排名表，则用 $N+1$ 行输出： - 第 $1$ 行输出 `Yes`。 - 第 $1+j$ 行（$1 \leq j \leq N$）输出最终获得第 $j$ 名的选手编号。

## 子任务 1.（$13$ 分）$N \leq 8$，$M \leq 8$。 2.（$16$ 分）$A_1,A_2,\dots,A_M,B_1,B_2,\dots,B_M$ 均为互不相同的数。 3.（$29$ 分）$N \leq 1\,000$，$M \leq 1\,000$。 4.（$23$ 分）对于第 $i$ 次（$2 \leq i \leq M$）排名变动，$A_i$ 和 $B_i$ 至少有一人并未出现在 $A_1, A_2, \dots, A_{i-1}, B_1, B_2, \dots, B_{i-1}$ 之中。 5.（$19$ 分）无附加约束。 ## 样例解释 1 假设比赛开始时，各名次对应的选手编号为 $(1,2,3,5,4)$（按第 $1$ 名至第 $N$ 名）。 此时，经过 $5$ 次排名变动，各轮结果如下： 1. 第 $1$ 次：第 $1$ 名的选手 $1$ 与第 $2$ 名的选手 $2$ 交换。交换后为 $(2,1,3,5,4)$。 2. 第 $2$ 次：第 $5$ 名的选手 $4$ 与第 $4$ 名的选手 $5$ 交换。交换后为 $(2,1,3,4,5)$。 3. 第 $3$ 次：第 $3$ 名的选手 $3$ 与第 $4$ 名的选手 $4$ 交换。交换后为 $(2,1,4,3,5)$。 4. 第 $4$ 次：第 $4$ 名的选手 $3$ 与第 $5$ 名的选手 $5$ 交换。交换后为 $(2,1,4,5,3)$。 5. 第 $5$ 次：第 $2$ 名的选手 $1$ 与第 $3$ 名的选手 $4$ 交换。交换后为 $(2,4,1,5,3)$。 因此，最终排名表为 $(2,4,1,5,3)$。 在所有不矛盾的排名表中，没有比 $(2,4,1,5,3)$ 字典序更小的结果。因此，输出 $(2,4,1,5,3)$。 此输入例同时满足子任务 $1,3,5$ 的约束。 ## 样例解释 2 不存在与笔记内容不矛盾的排名表。 此输入例同时满足子任务 $1,3,5$ 的约束。 ## 样例解释 3 此输入例满足所有子任务的约束。 ## 样例解释 4 此输入例满足子任务 $1,3,4,5$ 的约束。 ## 数据范围与约定 - $2 \leq N \leq 500\,000$。 - $1 \leq M \leq 500\,000$。 - $1 \leq A_i < B_i \leq N$（$1 \leq i \leq M$）。 - 所有输入均为整数。 由 ChatGPT 5 翻译