D - Neighbors Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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

どのように並べても全ての条件を満たすことはできません。

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.