

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) であって、以下の条件を満たすものが存在することをいいます。
制約
- 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
与えらえたグラフは下図のようであり、これはパスグラフです。
入力例 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:
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.