← 返回题目列表

AtCoder · abc287_c

E. 路径图?

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

给你一个简单的无向图 N 顶点和 M 边缘。 顶点已编号 1, 2, \dots, N,并且边缘已编号 1, 2, \dots, M.
边缘 i \, (i = 1, 2, \dots, M) 连接顶点 u_i 和 v_i.

确定该图是否是路径图。

什么是简单无向图? A 简单无向图 是一个没有自环或没有方向的多条边的图。

什么是路径图? 图表 N 顶点编号 1, 2, \dots, N 据说是 路径图 当且仅当存在序列 (v_1, v_2, \dots, v_N) 这是一个排列 (1, 2, \dots, 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