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>
def KnuthMorrisPratt(text, pattern):
    '''Yields all starting positions of copies of the pattern in the text.
    Calling conventions are similar to string.find, but its arguments can be
    lists or iterators, not just strings, it returns all matches, not just
    the first one, and it does not need the whole text in memory at once.
    Whenever it yields, it will have read the text exactly up to and including
the match that caused the yield.'''

    # allow indexing into pattern and protect against change during yield
    pattern = list(pattern)

    # build table of shift amounts
    shifts = [1] * (len(pattern) + 1)
    shift = 1
    for pos in xrange(len(pattern)):
        while shift <= pos and pattern[pos] != pattern[pos-shift]:
            shift += shifts[pos-shift]
        shifts[pos+1] = shift

    # do the actual search
    startPos = 0
    matchLen = 0
    for c in text:
        while matchLen == len(pattern) or \
              matchLen >= 0 and pattern[matchLen] != c:
            startPos += shifts[matchLen]
            matchLen -= shifts[matchLen]
        matchLen += 1
        if matchLen == len(pattern):
            yield startPos


def get_hash_of_set(st):
    p1 = 100003
    p2 = 10**9 + 7
    _hash = 0
    idx = 0
    mul = 1
    for element in sorted(st):
        _hash = (_hash + (element * mul)) % p2
        idx += 1
        mul = (mul * p1) % p2
    return _hash


n, m = map(int, raw_input().split())
d = {i: set() for i in xrange(1, n + 1)}
for _ in xrange(m):
    u, v = sorted(map(int, raw_input().split()))
    d[u].add(v - u)
    d[v].add(n - (v - u))

hashes = [get_hash_of_set(d[i]) for i in xrange(1, n + 1)]

# print(hashes)

text = hashes + hashes

cnt = 0
for startPos in KnuthMorrisPratt(text, hashes):
    # print(startPos)
    cnt += 1
    if cnt == 2:
        if startPos < n:
            print("Yes")
        else:
            print("No")
        exit(0)
