CF521E Cycling City

你正在城市街道上组织一场自行车比赛。该城市包含 $n$ 个路口，其中一些路口之间通过道路相连；每条道路都可以双向通行。没有两条道路会连接同一对路口，也没有道路会连接自身。 你希望比赛既能让专业运动员参与，也能让初学者参加，因此会举办三个组别：简单组、中等组和困难组。每个参赛者将根据自身情况选择适合的组别。对于每个组别，你都需要选择一条路线——一系列连续由道路相连的路口。所有路线必须满足以下条件： - 所有三条路线必须从同一个路口出发，并在同一个路口结束（起点与终点不能相同）； - 为了避免碰撞，任意两条路线之间不能有除起点和终点以外的公共路口，也不能经过相同的道路（无论方向）； - 每条路线都不能经过同一条路口两次，也不能经过同一条道路两次（无论第一次和第二次经过的方向）。 比赛的准备工作即将开始，你需要尽快确定比赛路线。路线的长度并不重要，只要满足所有上述要求即可。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 2 \cdot 10^{5}$），分别表示路口数和道路数。 接下来的 $m$ 行，每行包含两个整数，表示一条道路连接的两个路口的编号（路口编号从 $1$ 开始）。保证每对路口之间最多存在一条道路，也没有道路连接同一个路口。 请注意，不能保证任意两个路口都可以通过道路互通。

如果能够构造出符合要求的三条路线，第一行输出 “YES”。接下来的三行，每行输出一条路线，格式为 “$l\ p_{1}\ \cdots\ p_{l}$”，其中 $l$ 表示该路线上的路口数，$p_1,\ldots,p_l$ 按顺序给出路线经过的所有路口编号。 如果无法按照要求构造出三条路线，输出 “NO”。

由 ChatGPT 5 翻译