P14067 [PO Final 2022] 找环 / Monopol

Jocke 和他的朋友们经常一起玩大富翁。但在无数次游戏之后，他们对普通规则感到厌倦，于是稍微做了些改动： 首先他们会选择一个大小合适的国家。接着他们查看该国家的公路网，并选出若干城市，组成一个环（就像大富翁棋盘一样）。随后他们真的去到那个国家，开着车沿着这个环行驶，用真钱买卖地产来进行游戏。 不过有一个限制使得游戏实施起来很困难：他们必须在公路网里找到一个合适的环。有些国家的公路网非常庞大，更麻烦的是，这个环必须含有偶数条边，否则规则无法运行（“自由停车”不会落在中心，导致游戏不平衡）。 给定一张无向图，你的任务是在其中找到一个边数为偶数的环（偶环），如果存在的话。 ::::align{center}    图 1：三个样例对应图的示意。 ::::

第一行包含两个整数 $N$ 和 $M$，分别表示节点数与边数（$1 \le N \le 10^5$，$0 \le M \le \min(2 \cdot 10^5, \frac{N(N-1)}{2})$）。 接下来有 $M$ 行，每行包含两个整数 $a$ 和 $b$，表示图中在节点 $a$ 与节点 $b$ 之间有一条边（$1 \le a, b \le N$ 且 $a \ne b$）。保证图中同一对节点之间不存在多条边。

如果不存在偶环，输出一行字符串 $\texttt{NO}$。 如果存在偶环，输出一行字符串 $\texttt{YES}$。随后输出这样一个环：先输出一行一个偶数 $k$（$4 \le k \le N$），表示环中的节点数。下一行输出 $k$ 个两两不同的整数 $v_1, v_2, \ldots, v_k$（$1 \le v_i \le N$），用空格分隔，表示环上的节点，使得边 $(v_1, v_2), (v_2, v_3), \ldots, (v_{k-1}, v_k), (v_k, v_1)$ 都在图中出现。 如果有多种合法答案，输出任意一种均可被接受。

### 子任务 **本题采用捆绑测试。** | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | $1$ | $18$ | $N \le 10$ | | $2$ | $16$ | $N \le 100$ 且 $M \le 200$ | | $3$ | $17$ | 图是二分图 | | $4$ | $13$ | 图中所有节点的度数至多 $2$ | | $5$ | $20$ | 图中所有节点的度数至少 $3$ | | $6$ | $16$ | 无其他限制 |