Score : $400$ points

问题描述

确定是否存在一种方法，将编号为 $1$ 到 $N$ 的 $N$ 个人从左到右排成一行，以满足以下格式中的所有 $M$ 个条件。

• 条件格式：人员 $A_i$ 和人员 $B_i$ 是相邻的。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Determine whether there is a way to line up $N$ people, numbered $1$ to $N$, in a row side by side to satisfy all of the $M$ conditions in the following format.

• Condition: Person $A_i$ and Person $B_i$ are adjacent.

Constraints

• $2 \leq N \leq 10^5$
• $0 \leq M \leq 10^5$
• $1\leq A_i < B_i \leq N$
• All pairs $(A_i,B_i)$ are distinct.

Input

Input is given from Standard Input in the following format:

$N$ $M$

$A_1$ $B_1$

$\vdots$

$A_M$ $B_M$

Output

If there is a way to line up people to satisfy the conditions, print Yes; if not, print No.

Sample Input 1

4 2
1 3
2 3

Sample Output 1

Yes

One way to satisfy all the conditions is to line them up in the order $4,1,3,2$.

Sample Input 2

4 3
1 4
2 4
3 4

Sample Output 2

No

There is no way to line them up to satisfy all the conditions.

update @ 2024/3/10 10:04:49