← 返回题目列表

Codeforces · 1147/B

B. 克拉尼图

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

Inaka 有一个圆盘,其周长为 $$$n$$$ 单位。周长被从 $$$1$$$ 到 $$$n$$$ 顺时针编号的 $$$n$$$ 点等分,使得点 $$$i$$$ 和 $$$i + 1$$$ ($$$1 \leq i < n$$$) 相邻,点 $$$n$$$ 和 $$$1$$$ 也是相邻的。

圆盘上有$$$m$$$个直线段,其端点均在上述$$$n$$$点之中。

Inaka 想知道她的图像是否旋转对称,即是否存在整数 $$$k$$$ ($$$1 \leq k < n$$$),这样如果所有线段绕圆心顺时针旋转 $$$k$$$ 单位,则新图像将与原始图像相同。

输入

第一行包含两个空格分隔的整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 100\,000$$$, $$$1 \leq m \leq 200\,000$$$) — 分别是点的数量和段的数量。

以下 $$$m$$$ 行中的第 $$$i$$$ 行包含两个空格分隔的整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$),它们描述连接点 $$$a_i$$$ 和 $$$a_i$$$ 的线段$$$b_i$$$。

保证没有线段重合。

输出

输出一行 - 如果图像旋转对称,则输出“是”,否则输出“否”(均不包括引号)。

您可以以任何大小写(大写或小写)输出每个字母。

示例

输入 #1

12 6
1 3
3 7
5 7
7 11
9 11
11 3

输出 #1

Yes

输入 #2

9 6
4 5
5 6
7 8
8 9
1 2
2 3

输出 #2

Yes

输入 #3

10 3
1 2
3 2
7 2

输出 #3

No

输入#4

10 2
1 6
2 7

输出#4

Yes

注意

前两个示例如下所示。围绕中心顺时针旋转 $$$120$$$ 度后,两个图像都与各自的原始图像相同。