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

AT_abc231_d.[ABC231D] Neighbors

普及-

通过率：0%

AC君温馨提醒

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

题目描述

请判断是否存在一种将编号为 11 到 NN 的 NN 个人横向一字排开的排列方式，使得以下 MM 个条件全部成立。

  • 条件：第 AiA_i 个人与第 BiB_i 个人必须相邻。

输入格式

输入以如下格式从标准输入给出。

NN MM
A1A_1 B1B_1
⋮\vdots
AMA_M BMB_M

输出格式

如果存在满足所有条件的排列方式，输出 Yes；否则输出 No。

输入输出样例

  • 输入#1

    4 2
1 3
2 3

    输出#1

    Yes

  • 输入#2

    4 3
1 4
2 4
3 4

    输出#2

    No

说明/提示

限制条件

  • 2≤N≤1052 \leq N \leq 10^5
  • 0≤M≤1050 \leq M \leq 10^5
  • 1≤Ai<Bi≤N1 \leq A_i < B_i \leq N
  • (Ai,Bi)(A_i, B_i) 互不相同

样例解释 1

例如，将 4,1,3,24, 1, 3, 2 按此顺序排列，可以满足所有条件。

样例解释 2

无论如何排列，都无法满足所有条件。

由 ChatGPT 4.1 翻译

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

首页