#D613. Chladni Figure
Chladni Figure
Chladni Figure
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 ≤ 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 ≤ 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
The first line contains two space-separated integers n and m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 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 ≤ a_i, b_i ≤ n, a_i ≠ b_i) that describe a segment connecting points a_i and b_i.
It is guaranteed that no segments coincide.
Output
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).
Examples
Input
12 6 1 3 3 7 5 7 7 11 9 11 11 3
Output
Yes
Input
9 6 4 5 5 6 7 8 8 9 1 2 2 3
Output
Yes
Input
10 3 1 2 3 2 7 2
Output
No
Input
10 2 1 6 2 7
Output
Yes
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.
inputFormat
Input
The first line contains two space-separated integers n and m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 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 ≤ a_i, b_i ≤ n, a_i ≠ b_i) that describe a segment connecting points a_i and b_i.
It is guaranteed that no segments coincide.
outputFormat
Output
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).
Examples
Input
12 6 1 3 3 7 5 7 7 11 9 11 11 3
Output
Yes
Input
9 6 4 5 5 6 7 8 8 9 1 2 2 3
Output
Yes
Input
10 3 1 2 3 2 7 2
Output
No
Input
10 2 1 6 2 7
Output
Yes
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.
样例
10 2
1 6
2 7
Yes