路径图?

题目描述

给定一个由 $N$ 个顶点和 $M$ 条边组成的简单无向图。顶点编号为 $1, 2, \dots, N$,边编号为 $1, 2, \dots, M$。

第 $i$ 条边 ($i = 1, 2, \dots, M$) 连接顶点 $u_i$ 和 $v_i$。

判断该图是否为路径图。

什么是简单无向图? 简单无向图是指没有自环和重边,且边没有方向的图。

什么是路径图? 顶点编号为 $1, 2, \dots, 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$ 的边。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

输出格式

若给定的图是路径图,输出 Yes,否则输出 No。

样例

4 3
1 3
4 2
3 2

Yes

给定的图是一个路径图。

2 0

No

给定的图不是路径图。

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

No

给定的图不是路径图。

数据范围

• $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$)
• 输入中的所有值均为整数。
• 给定的图是简单图。