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>
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashSet;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.util.HashMap;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jenish
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        DChladniFigure solver = new DChladniFigure();
        solver.solve(1, in, out);
        out.close();
    }

    static class DChladniFigure {
        int[][] ar;
        int n;
        int m;
        HashMap<Integer, HashSet<Integer>> hashSetHashSet;

        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            n = in.scanInt();
            m = in.scanInt();
            boolean f = false;
            hashSetHashSet = new HashMap<>();
            for (int i = 0; i < n; i++) hashSetHashSet.put(i, new HashSet<>());
            ar = new int[m][2];
            for (int i = 0; i < m; i++) {
                int x = in.scanInt() - 1;
                int y = in.scanInt() - 1;
                if (y < x) {
                    int t = x;
                    x = y;
                    y = t;
                }
                ar[i][0] = x;
                ar[i][1] = y;
                hashSetHashSet.get(x).add(y);
            }
            for (int i = 1; i * i <= n; i++) {
                if (n % i == 0) {
                    f |= check(i);
                    if (i != 1 && i * i != n) f |= check(n / i);
                }
            }
            out.println((f) ? "Yes" : "No");
        }

        boolean check(int k) {
            HashMap<Integer, HashSet<Integer>> hs = new HashMap<>();
            for (int i = 0; i < n; i++) hs.put(i, new HashSet<>());
            for (int i = 0; i < m; i++) {
                int x = (ar[i][0] + k) % n, y = (ar[i][1] + k) % n;
                if (y < x) {
                    int t = x;
                    x = y;
                    y = t;
                }
                if (hashSetHashSet.get(x).contains(y)) hs.get(x).add(y);
                else return false;
            }
            for (int i = 0; i < n; i++) {
                if (hashSetHashSet.get(i).size() != hs.get(i).size()) return false;
            }
            return true;
        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int INDEX;
        private BufferedInputStream in;
        private int TOTAL;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (INDEX >= TOTAL) {
                INDEX = 0;
                try {
                    TOTAL = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (TOTAL <= 0) return -1;
            }
            return buf[INDEX++];
        }

        public int scanInt() {
            int I = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    I *= 10;
                    I += n - '0';
                    n = scan();
                }
            }
            return neg * I;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}

