#1966. P7771 【模板】欧拉路径

P7771 【模板】欧拉路径

【模板】欧拉路径

题目描述

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

输入格式

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

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

输出格式

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

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

样例 #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

样例输入 #2

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

样例输出 #2

1 2 3 4 3 5

样例 #3

样例输入 #3

4 3
1 2
1 3
1 4

样例输出 #3

No

提示

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

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

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

数据生成器