弦图识别（Chordal Graph Recognition）

问题描述

给定一个简单无向图，含 $N$ 个顶点和 $M$ 条边。第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。

• 一个图是弦图（chordal graph），当且仅当它不含长度 $\ge 4$ 的诱导环（即任意长度 $\ge 4$ 的环都至少有一条弦）。
• 一个完美消去序（perfect elimination ordering）是一个顶点排列 $v_0, v_1, \dots, v_N$，使得对每个 $i$，顶点 $v_i$ 在子图 $G[\{v_i, v_{i+1}, \dots, v_N\}]$ 中的邻居构成一个团。

已知：图是弦图 当且仅当 它存在完美消去序。

要求：

• 若图是弦图，输出任意一个完美消去序；
• 否则，输出任意一个长度 $\ge 4$ 的诱导环。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^5$
• $0 \leq a_i, b_i < N$
• $a_i \ne b_i$
• $\{a_i, b_i\} \ne \{a_j, b_j\}$（$i \ne j$）

输入

$N\ M$
$a_0\ b_0$
$a_1\ b_1$
:
$a_{M-1}\ b_{M-1}$

输出

若图非弦图：

NO
$K$
$c_0\ c_1\ \cdots\ c_{K-1}$

其中 $K \ge 4$ 是诱导环长度，$c_i$ 是环上顶点（按环顺序，可为任意起点与方向）。

若图是弦图：

YES
$v_0\ v_1\ \cdots\ v_{N-1}$

其中 $v_i$ 是完美消去序中的第 $i$ 个顶点（0-indexed）。

4 4
1 3
0 3
1 2
0 1

YES
2 0 1 3

5 4
0 2
1 3
0 1
3 2

NO
4
1 3 2 0

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

NO
5
6 3 2 9 5