Chladni Figure
Contest: Forethought Future Cup - Final Round (Onsite Finalists Only)
Difficulty rating: 1900
Tags: brute force, strings

Inaka has a disc, the circumference of which is $$$n$$$ units. The circumference is equally divided by $$$n$$$ points numbered clockwise from $$$1$$$ to $$$n$$$, such that points $$$i$$$ and $$$i + 1$$$ ($$$1 \leq i < n$$$) are adjacent, and so are points $$$n$$$ and $$$1$$$.

There are $$$m$$$ straight segments on the disc, the endpoints of which are all among the aforementioned $$$n$$$ points.

Inaka wants to know if her image is rotationally symmetrical, i.e. if there is an integer $$$k$$$ ($$$1 \leq k < n$$$), such that if all segments are rotated clockwise around the center of the circle by $$$k$$$ units, the new image will be the same as the original one.

Input format:
The first line contains two space-separated integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 100\,000$$$, $$$1 \leq m \leq 200\,000$$$) — the number of points and the number of segments, respectively.

The $$$i$$$-th of the following $$$m$$$ lines contains two space-separated integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$) that describe a segment connecting points $$$a_i$$$ and $$$b_i$$$.

It is guaranteed that no segments coincide.

Output format:
Output one line — "Yes" if the image is rotationally symmetrical, and "No" otherwise (both excluding quotation marks).

You can output each letter in any case (upper or lower).

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
The first two examples are illustrated below. Both images become the same as their respective original ones after a clockwise rotation of $$$120$$$ degrees around the center.

Example input:
12 6
1 3
3 7
5 7
7 11
9 11
11 3

Example output:
Yes

Example input:
9 6
4 5
5 6
7 8
8 9
1 2
2 3

Example output:
Yes

Editorial:
Let's brute force the value of $$$k$$$ and check if it's possible to rotate the image by $$$k$$$ to get the same image. We can do this by iterating through all segments $$$(a,b)$$$, and checking that $$$(a+k,b+k)$$$ is a segment (the endpoints taken modulo $$$n$$$ if needed).
This gives an $$$O(nm)$$$ solution, however, you can notice that we only need to check divisors of $$$n$$$ rather than all values from $$$1$$$ to $$$n$$$. This is because the set of segments $$$(a,b), (a+k,b+k), (a+2k,b+2k), \ldots$$$ is exactly equal to $$$(a,b), (a+\gcd(n,k), b+\gcd(n,k)), (a+2\gcd(n,k), b+2\gcd(n,k)), \ldots$$$. Thus, this take $$$O(m \cdot d(n))$$$, where $$$d(n)$$$ denotes the number of divisors of $$$n$$$, which is fast enough to pass this problem.
There is also a faster linear time solution. We can reduce this to a problem of finding the largest period of a string. For every point, we can sort the length of the segments starting from that point (length in this case refers to clockwise distance). We also add some null character to denote a point. For instance, the first sample case's string might start like $$$2, -1, -1, 4, 8, 10, -1, \ldots$$$ that represent the points from $$$1$$$ to $$$3$$$. Such a string can be computed in $$$O(m \log m)$$$ time. Then, after finding this string, we just want to check the period is bigger than $$$1$$$. Let $$$w$$$ be the length of the string. We can find this by concatenating the string to itself, then use z-algorithm to check if there is any is any index $$$i$$$ from $$$1$$$ to $$$w-1$$$ that is at least $$$w$$$.