AT_abc287_c [ABC287C] Path Graph?

题目描述

给定一个有 $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$ 个顶点的图，如果存在一个由这些顶点的某种排列 $(v_1, v_2, \dots, v_N)$，满足以下条件，则称该图为路径图：

• 对于所有 $i = 1, 2, \dots, N-1$，存在一条边连接顶点 $v_i$ 和 $v_{i+1}$；
• 对于所有满足 $1 \leq i, j \leq N$ 且 $|i - j| \geq 2$ 的整数 $i, j$，不存在边连接顶点 $v_i$ 和 $v_j$。

输入格式

输入按以下格式从标准输入读入。

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

输出格式

如果给定的图是路径图，输出 Yes；否则输出 No。

输入输出样例 #1

输入 #1

4 3
1 3
4 2
3 2

输出 #1

Yes

输入输出样例 #2

输入 #2

2 0

输出 #2

No

输入输出样例 #3

输入 #3

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

输出 #3

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 \quad (i = 1, 2, \dots, M)$
• 输入的所有值均为整数
• 输入保证图为简单无向图

样例解释 1

给定的图如下图所示，是一个路径图。

样例解释 2

给定的图如下图所示，不是路径图。

样例解释 3

给定的图如下图所示，不是路径图。

由 ChatGPT 4.1 翻译