5797 - 提高:图论:欧拉回路 模板题
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^5,m\leq 2\times 10^5。
保证将有向边视为无向边后图连通。