You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

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

题目描述

共有 $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<b_k$。

输入格式

第一行输入两个整数 $N,M$。

接下来 $M$ 行，每行输入两个整数 $A_i,B_i$。

输出格式

如果不存在满足条件的排名表，输出一行一个字符串 No。

如果存在满足条件的排名表：

• 第一行输出一个字符串 Yes；
• 第 $j+1(1\le j\le N)$ 行输出一个整数 $P_j$，其中 $P$ 表示满足条件且字典序最小的排名表。

5 5
1 2
4 5
3 4
3 5
1 4

Yes
2
4
1
5
3

3 4
1 3
2 3
1 3
2 3

No

8 3
1 8
3 5
4 7

Yes
1
8
2
3
5
4
7
6

6 5
1 2
1 3
1 4
1 5
1 6

Yes
1
6
5
4
3
2

提示

【样例解释 #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<B_i\le N(1\le i\le M)$。

【子任务】

1. （$13$ 分）$N,M\le 8$；
2. （$16$ 分）$A_1,A_2,\ldots,A_M,B_1,B_2,\ldots,B_M$ 两两不同；
3. （$29$ 分）$N,M\le 1000$；
4. （$23$ 分）在第 $i(2\le i\le M)$ 次排名变化中，$A_i$ 和 $B_i$ 中至少有一个值在 $A_1,A_2,\ldots,A_{i-1},B_1,B_2,\ldots,B_{i-1}$ 中没有出现；
5. （$19$ 分）无附加限制。