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.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;
import java.util.*;

public class ChladniFig {

    // begin of solution
    static class Point implements Comparator<Point> {
        int x, y;

        Point() {
            x = 0;
            y = 0;
        }

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compare(Point o1, Point o2) {
            int xComp = Integer.compare(o1.x, o2.x);
            int yComp = Integer.compare(o1.y, o2.y);
            if (xComp == 0) {
                return ((yComp == 0) ? xComp : yComp);
            } else {
                return xComp;
            }
        }
    }

    private static boolean equivalence(ArrayList<Point> s1, ArrayList<Point> s2) {
        int l = s1.size();
        for (int i = 0; i < l; i++) {
            if (s1.get(i).x != s2.get(i).x || s1.get(i).y != s2.get(i).y)
                return false;
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        AmitScan sc = new AmitScan();
        AmitPrint pr = new AmitPrint();
        int n = sc.scanInt();
        int m = sc.scanInt();
        ArrayList<Point> set = new ArrayList<>();
        int x, y;
        for (int i = 0; i < m; i++) {
            x = sc.scanInt() - 1;
            y = sc.scanInt() - 1;
            if (x < y)
                set.add(new Point(x, y));
            else set.add(new Point(y, x));
        }
        set.sort(new Point());
        ArrayList<Point> set1;
        for (int i = 1; i < n; i++) {
            if (n % i != 0)
                continue;
            set1 = new ArrayList<>();
            for (Point p : set) {
                int nx = ((p.x + i) % n);
                int ny = ((p.y + i) % n);
                if (ny > nx)
                    set1.add(new Point(nx, ny));
                else set1.add(new Point(ny, nx));
            }
            set1.sort(new Point());
//            for (Point p : set2)
//                pr.println(p.x + " " + p.y);
//            pr.println("");
            if (equivalence(set, set1)) {
                pr.println("Yes");
                pr.close();
                return;
            }
        }
        pr.println("No");
        pr.close();
    }
    // end of solution

    static class AmitScan {
        private byte[] buf = new byte[1024]; // Buffer of Bytes
        private int index;
        private InputStream in;
        private int total;

        AmitScan() {
            in = System.in;
        }

        private int scan() throws IOException // Scan method used to scan buf
        {
            if (total < 0)
                throw new InputMismatchException();
            if (index >= total) {
                index = 0;
                total = in.read(buf);
                if (total <= 0)
                    return -1;
            }
            return buf[index++];
        }

        String scanString() throws IOException {
            StringBuilder sb = new StringBuilder();
            int n = scan();
            while (isWhiteSpace(n))
                n = scan();
            while (!isWhiteSpace(n)) {
                sb.append((char) n);
                n = scan();
            }
            return sb.toString();
        }

        int scanInt() throws IOException {
            int integer = 0;
            int n = scan();
            while (isWhiteSpace(n)) // Removing starting whitespaces
                n = scan();
            int neg = 1;
            if (n == '-') // If Negative Sign encounters
            {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    integer *= 10;
                    integer += n - '0';
                    n = scan();
                } else
                    throw new InputMismatchException();
            }
            return neg * integer;
        }

        long scanLong() throws IOException {
            long integer = 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') {
                    integer *= 10;
                    integer += n - '0';
                    n = scan();
                } else
                    throw new InputMismatchException();
            }
            return neg * integer;
        }

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

    static class AmitPrint {
        private final BufferedWriter bw;

        AmitPrint() {
            this.bw = new BufferedWriter(new OutputStreamWriter(System.out));
        }

        private void print(Object object) throws IOException {
            bw.append("").append(String.valueOf(object));
        }

        void println(Object object) throws IOException {
            print(object);
            bw.append("\n");
        }

        void close() throws IOException {
            bw.close();
        }

        void flush() throws IOException {
            bw.flush();
        }
    }
}