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

通过次数

33

提交次数

48

Time Limit : 1 秒
Memory Limit : 128 MB

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

Input

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

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

Output

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

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

Examples

Input

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

Output

1 2 1 3 3 4 2

Input

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

Output

1 2 3 4 3 5

Input

4 3
1 2
1 3
1 4

Output

No

Hint

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

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

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