【模板】欧拉路径

题目描述

求有向图字典序最小的欧拉路径。

输入输出格式

输入格式


第一行两个整数 $n,m$ 表示有向图的点数和边数。 接下来 $m$ 行每行两个整数 $u,v$ 表示存在一条 $u\to v$ 的有向边。

输出格式


如果不存在欧拉路径,输出一行 `No`。 否则输出一行 $m+1$ 个数字,表示字典序最小的欧拉路径。

输入输出样例

输入样例 #1

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

输出样例 #1

1 2 1 3 3 4 2

输入样例 #2

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

输出样例 #2

1 2 3 4 3 5

输入样例 #3

4 3
1 2
1 3
1 4

输出样例 #3

No

说明

对于 $50\%$ 的数据,$n,m\leq 10^3$。 对于 $100\%$ 的数据,$1\leq u,v\leq n\leq 10^5$,$m\leq 2\times 10^5$。 保证将有向边视为无向边后图连通。 [数据生成器](https://www.luogu.com.cn/paste/9oswk47n)