← 返回题目列表

AtCoder · abc404_c

E. 循环图?

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

分数: 300 点

问题陈述

给你一个简单的无向图 N 顶点和 M 边缘。顶点已编号 1,2,\dots,N 且边缘已编号 1,2,\dots,M。边缘 i 连接顶点 A_i 和 B_i.

判断该图是否为循环图。

简单无向图的定义 简单无向图是具有无向边、没有自环或多边的图。

循环图的定义 An N- 带有标记顶点的顶点图 1,2,\dots,N 是存在排列时的循环图 (v_1,v_2,\dots,v_N) of (1,2,\dots,N) 这样:
  • 对于每个 i = 1,2,\dots,N-1,顶点之间有一条边 v_i 和 v_{i+1}.
  • 顶点之间有一条边 v_N 和 v_1.
  • 不存在其他边。

约束

  • 3 \le N \le 2\times 10^5
  • 0 \le M \le 2\times 10^5
  • 1 \le A_i, B_i \le N
  • 给定的图表很简单。
  • 所有输入值均为整数。

输入

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

N M
A_1 B_1
\vdots
A_M B_M

输出

输出 Yes 如果给定的图是循环图;否则,打印 No.


示例输入 1

4 4
2 4
3 1
4 1
2 3

示例输出 1

Yes

给出的图如下,这是一个循环图。

Figure


示例输入 2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

示例输出 2

No

给定的图表如下,这不是循环图。

Figure