Preparando MOJI
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.
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 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).
12 6 1 3 3 7 5 7 7 11 9 11 11 3
Yes
9 6 4 5 5 6 7 8 8 9 1 2 2 3
Yes
10 3 1 2 3 2 7 2
No
10 2 1 6 2 7
Yes
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.
Informação
Provedor Codeforces
Código CF1147B
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 09:46:39
Relacionados