Contest Duration: - (local time) (100 minutes) Back to Home
C - Path Graph? /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1, 2, \dots, N の番号が、辺には 1, 2, \dots, M の番号が付けられています。
i \, (i = 1, 2, \dots, M) は頂点 u_i, v_i を結んでいます。

このグラフがパスグラフであるか判定してください。

パスグラフとは 頂点に 1, 2, \dots, N の番号が付けられたN 頂点のグラフがパスグラフであるとは、(1, 2, \dots, N) を並べ変えて得られる数列 (v_1, v_2, \dots, v_N) であって、以下の条件を満たすものが存在することをいいます。
• 全ての i = 1, 2, \dots, N-1 に対して、頂点 v_i, v_{i+1} を結ぶ辺が存在する
• 整数 i, j1 \leq i, j \leq N, |i - j| \geq 2 を満たすならば、頂点 v_i, v_j を結ぶ辺は存在しない

### 制約

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
• 入力される値は全て整数
• 入力で与えられるグラフは単純

### 入力

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M


### 入力例 1

4 3
1 3
4 2
3 2


### 出力例 1

Yes


### 入力例 2

2 0


### 出力例 2

No


### 入力例 3

5 5
1 2
2 3
3 4
4 5
5 1


### 出力例 3

No


Score : 300 points

### Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, 2, \dots, N, and the edges are numbered 1, 2, \dots, M.
Edge i \, (i = 1, 2, \dots, M) connects vertices u_i and v_i.

Determine if this graph is a path graph.

What is a simple undirected graph? A simple undirected graph is a graph without self-loops or multiple edges whose edges do not have a direction.

What is a path graph? A graph with N vertices numbered 1, 2, \dots, N is said to be a path graph if and only if there is a sequence (v_1, v_2, \dots, v_N) that is a permutation of (1, 2, \dots, N) and satisfies the following conditions:
• For all i = 1, 2, \dots, N-1, there is an edge connecting vertices v_i and v_{i+1}.
• If integers i and j satisfies 1 \leq i, j \leq N and |i - j| \geq 2, then there is no edge that connects vertices v_i and v_j.

### Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
• All values in the input are integers.
• The graph given in the input is simple.

### Input

The input is given from Standard Input in the following format:

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M


### Output

Print Yes if the given graph is a path graph; print No otherwise.

### Sample Input 1

4 3
1 3
4 2
3 2


### Sample Output 1

Yes


Illustrated below is the given graph, which is a path graph.

### Sample Input 2

2 0


### Sample Output 2

No


Illustrated below is the given graph, which is not a path graph.

### Sample Input 3

5 5
1 2
2 3
3 4
4 5
5 1


### Sample Output 3

No


Illustrated below is the given graph, which is not a path graph.