【题目描述】
给定一个简单无向无权图,由
如果一个图不包含长度为四或更长的诱导环,则称其为弦图。
完美消除序列是顶点的一个排列,使得对于每个顶点
如果图是弦图,请找出一个完美消除序列。如果存在多个完美消除序列,输出任意一个即可。
如果图不是弦图,请找出一个长度为四或更长的诱导环。如果存在多个这样的环,输出任意一个即可。
【输入】
$N$ $M$
$a_0$ $b_0$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{M - 1}$ $b_{M - 1}$【输出】
如果图不是弦图,请按以下格式输出一个长度为四或更长的诱导环。
NO
$K$
$c_0$ $c_1$ $\ldots$ $c_K$如果图是弦图,请按以下格式输出一个完美消除序列。
YES
$v_0$ $v_1$ $\ldots$ $v_N$【输入样例】
4 4
1 3
0 3
1 2
0 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【数据范围】
【来源】
Library Checker(yosupo06) chordal_graph_recognition
本题为 special judge(输出任意合法解),暂不可本地评测。