Neighbors

题目描述

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

条件：人 $A_i$ 和人 $B_i$ 相邻。

输入格式

输入从标准输入给出，格式如下： $N$ $M$ $A_1$ $B_1$ $\vdots$ $A_M$ $B_M$

输出格式

如果存在一种排列使人满足这些条件，输出 $Yes$；如果不存在，输出 $No$。

4 2
1 3
2 3

Yes

4 3
1 4
2 4
3 4

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)$ 都是不同的。一种满足所有条件的方法是按顺序排列为 $4,1,3,2$.
不存在一种排列可以满足所有条件。

标签: AtCoder|abc231D

来源

AtCoder|abc231D