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.

<image>
from sys import stdin


def factorize(n):  # o(sqr(n))
    c, ans = 2, [1]
    while (c * c < n):
        if n % c == 0:
            ans.extend([c, n // c])
        c += 1

    if c * c == n:
        ans.append(c)
    return ans


def fast2():
    import os, sys, atexit
    from cStringIO import StringIO as BytesIO
    # range = xrange
    sys.stdout = BytesIO()
    atexit.register(lambda: os.write(1, sys.stdout.getvalue()))
    return BytesIO(os.read(0, os.fstat(0).st_size)).readline


def cycle():
    for j in factorize(len(diff)):
        dis = set()
        for k in range(0, len(diff), j):
            dis.add(tuple(diff[k:k + j]))

        if len(dis) == 1:
            return False

    return True


input = fast2()
rints = lambda: [int(x) for x in input().split()]
n, m = rints()
adj, diff, a = [[] for _ in range(n + 1)], [], [rints() for _ in range(m)]

for x, y in a:
    adj[x].append(y)
    adj[y].append(x)

for i in range(1, n + 1):
    tem, tem2 = 0, []
    for j in adj[i]:
        d = (j - i) % n
        if d <= (n >> 1):
            tem2.append(d)
            tem += 1

    if not tem:
        tem2.append(tem)

    diff.extend(sorted(tem2))

print('Yes' if not cycle() else 'No')
