102313: [AtCoder]ABC231 D - Neighbors

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $400$ points

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.

Input

题意翻译

是否存在一种 $N$ 的排列,满足以下 $M$ 个条件: - $A_i$ 和 $B_i$ 相邻 保证所有的 $(A_i,B_i)$ 都是不同的。

Output

分数:400分

问题描述

判断是否有一种方式将编号为1到N的N个人排成一行,相邻的方式满足以下M个条件。

  • 条件:编号为A_i和B_i的人相邻。

限制条件

  • $2 \leq N \leq 10^5$
  • $0 \leq M \leq 10^5$
  • $1\leq A_i < B_i \leq N$
  • 所有对$(A_i,B_i)$都是不同的。

输入

输入将以以下格式从标准输入给出:

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

输出

如果有办法按照条件排列人,打印Yes;如果没有,打印No


样例输入1

4 2
1 3
2 3

样例输出1

Yes

一种满足所有条件的排列方式是按顺序排列4、1、3、2。


样例输入2

4 3
1 4
2 4
3 4

样例输出2

No

没有一种方式可以按照条件排列他们。

加入题单

上一题 下一题 算法标签: