AT_abc231_d [ABC231D] Neighbors

题目描述

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

• 条件：第 $A_i$ 个人与第 $B_i$ 个人必须相邻。

输入格式

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

$N$ $M$
$A_1$ $B_1$
$\vdots$
$A_M$ $B_M$

输出格式

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

输入输出样例 #1

输入 #1

4 2
1 3
2 3

输出 #1

Yes

输入输出样例 #2

输入 #2

4 3
1 4
2 4
3 4

输出 #2

No

说明/提示

限制条件

• $2 \leq N \leq 10^5$
• $0 \leq M \leq 10^5$
• $1 \leq A_i < B_i \leq N$
• $(A_i, B_i)$ 互不相同

样例解释 1

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

样例解释 2

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

由 ChatGPT 4.1 翻译