Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Chladni Figure

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputInaka 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

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

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.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/08/2020 08:26:16 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|