C - Path Graph? Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

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, j が 1 \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

出力

与えられたグラフがパスグラフなら Yes、そうでないなら No と出力せよ。

入力例 1

4 3
1 3
4 2
3 2

出力例 1

Yes

与えらえたグラフは下図のようであり、これはパスグラフです。

example_00

入力例 2

2 0

出力例 2

No

与えらえたグラフは下図のようであり、これはパスグラフではありません。

example_01

入力例 3

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

出力例 3

No

与えらえたグラフは下図のようであり、これはパスグラフではありません。

example_02

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.

example_00

Sample Input 2

2 0

Sample Output 2

No

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

example_01

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.

example_02