QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 2048 MB Hackable ✓
[0]

# 21755. 弦图判定

Statistics

Source: Library Checker

给定一张 N 个点 M 条边的无向图,你需要判定其是否为一张弦图

如果其是弦图,你还需要给出任意完美消除序列。如果不是弦图,你需要给出其长度大于等于 4 且不包含弦的环。

输入格式

输入的第一行包含两个整数 NM

接下来 M 行,每行两个整数 x,y,描述一条边。保证图中没有重边与自环。

输出格式

若给定的图不是弦图:

  • 输出一行 NO
  • 接下来一行,包含一个整数 K,表示你找到的环的环长。
  • 接下来一行,包含 K 个整数 v0,v1,,vK1,描述你的环。

若给定的图是弦图:

  • 输出一行 YES
  • 接下来一行,包含 N 个整数 u0,u1,,uN1,描述完美消除序列。

如果有多种合法的解,你可以输出任意一种。

样例数据

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

子任务

对于所有数据,1N2×1051M2×1050x,y<Nxy。图中没有重边与资环。