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

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.

 [Image]

Difficulty: interview

Starter code:

Solutions:
import math


class CodeforcesTask1147BSolution:
    def __init__(self):
        self.result = ''
        self.n_m = []
        self.points = []

    def read_input(self):
        self.n_m = [int(x) for x in input().split(" ")]
        for x in range(self.n_m[1]):
            self.points.append([int(y) for y in input().split(" ")])

    def process_task(self):
        can = False
        segm = {}
        for point in self.points:
            segm["{0}_{1}".format(*point)] = True
            segm["{1}_{0}".format(*point)] = True
        for k in range(1, self.n_m[0]):
            if not self.n_m[0] % k:
                #print(k)
                do = True
                for p in self.points:
                    a, b = (p[0] + k) % self.n_m[0], (p[1] + k) % self.n_m[0]
                    if not a:
                        a = self.n_m[0]
                    if not b:
                        b = self.n_m[0]
                    if not "{0}_{1}".format(a, b) in segm:
                        do = False
                        break
                if do:
                    can = do
                    break
        self.result = "Yes" if can else "No"

    def get_result(self):
        return self.result


def __starting_point():
    Solution = CodeforcesTask1147BSolution()
    Solution.read_input()
    Solution.process_task()
    print(Solution.get_result())

__starting_point()

def check(k,g):
    for i in g:
        a = (i[0] + k) % n
        b = (i[1] + k) % n
        if not (min(a, b), max(a, b)) in g:
            return False
    return True

n, m =[int(i) for i in input().split()]

g = set()
for i in range(m):
    a, b = [int(i) for i in input().split()]
    a -= 1
    b -= 1
    # usar tupla ao inves de uma lista pois tuplas sao hashable
    g.add((min(a, b), max(a, b)))
 
for i in range(1, n):
    if n % i == 0:
        if not check(i,g):
            continue
        print('Yes')
        break
else:
    print('No')
# else depois de um for é executado se ele n quebrar