Source: Library Checker
给定一张 N 个点 M 条边的无向图,你需要判定其是否为一张弦图。
如果其是弦图,你还需要给出任意完美消除序列。如果不是弦图,你需要给出其长度大于等于 4 且不包含弦的环。
输入格式
输入的第一行包含两个整数 N 和 M。
接下来 M 行,每行两个整数 x,y,描述一条边。保证图中没有重边与自环。
输出格式
若给定的图不是弦图:
- 输出一行
NO
。 - 接下来一行,包含一个整数 K,表示你找到的环的环长。
- 接下来一行,包含 K 个整数 v0,v1,⋯,vK−1,描述你的环。
若给定的图是弦图:
- 输出一行
YES
。 - 接下来一行,包含 N 个整数 u0,u1,⋯,uN−1,描述完美消除序列。
如果有多种合法的解,你可以输出任意一种。
样例数据
样例 1 输入
4 4
1 3
0 3
1 2
0 1
样例 1 输出
YES
2 0 1 3
样例 2 输入
5 4
0 2
1 3
0 1
3 2
样例 2 输出
NO
4
1 3 2 0
样例 3 输入
10 15
0 1
1 2
2 3
3 4
4 0
5 6
6 7
7 8
8 9
9 5
0 5
1 7
2 9
3 6
4 8
样例 3 输出
NO
5
6 3 2 9 5
子任务
对于所有数据,1≤N≤2×105,1≤M≤2×105,0≤x,y<N,x≠y。图中没有重边与资环。