题目详情题解（0）讨论（0）提交记录（0）

CF521E.Cycling City

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

你正在城市街道上组织一场自行车比赛。该城市包含 nn 个路口，其中一些路口之间通过道路相连；每条道路都可以双向通行。没有两条道路会连接同一对路口，也没有道路会连接自身。

你希望比赛既能让专业运动员参与，也能让初学者参加，因此会举办三个组别：简单组、中等组和困难组。每个参赛者将根据自身情况选择适合的组别。对于每个组别，你都需要选择一条路线——一系列连续由道路相连的路口。所有路线必须满足以下条件：

  • 所有三条路线必须从同一个路口出发，并在同一个路口结束（起点与终点不能相同）；
  • 为了避免碰撞，任意两条路线之间不能有除起点和终点以外的公共路口，也不能经过相同的道路（无论方向）；
  • 每条路线都不能经过同一条路口两次，也不能经过同一条道路两次（无论第一次和第二次经过的方向）。

比赛的准备工作即将开始，你需要尽快确定比赛路线。路线的长度并不重要，只要满足所有上述要求即可。

输入格式

第一行包含两个整数 nn 和 mm（1≤n,m≤2⋅1051 \leq n, m \leq 2 \cdot 10^{5}），分别表示路口数和道路数。

接下来的 mm 行，每行包含两个整数，表示一条道路连接的两个路口的编号（路口编号从 11 开始）。保证每对路口之间最多存在一条道路，也没有道路连接同一个路口。

请注意，不能保证任意两个路口都可以通过道路互通。

输出格式

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

如果无法按照要求构造出三条路线，输出 “NO”。

输入输出样例

  • 输入#1

    4 4
1 2
2 3
3 4
4 1

    输出#1

    NO

  • 输入#2

    5 6
1 2
1 3
1 4
2 5
3 5
4 5

    输出#2

    YES
3 5 4 1
3 5 3 1
3 5 2 1

说明/提示

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页