5797 - 提高:图论:欧拉回路 模板题

通过次数

33

提交次数

48

时间限制 : 1 秒
内存限制 : 128 MB

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

输入

第一行两个整数 n,m 表示有向图的点数和边数。

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

输出

如果不存在欧拉路径,输出一行 No

否则输出一行 m+1 个数字,表示字典序最小的欧拉路径。

样例

输入

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

输出

1 2 1 3 3 4 2

输入

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

输出

1 2 3 4 3 5

输入

4 3
1 2
1 3
1 4

输出

No

提示

对于 50\% 的数据,n,m\leq 10^3

对于 100\% 的数据,1\leq u,v\leq n\leq 10^5m\leq 2\times 10^5

保证将有向边视为无向边后图连通。