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.util.*;
import java.io.*;

public class DD {
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
//        Point[] points = new Point[N];
        ArrayList<Integer>[] graph = new ArrayList[N];
        for(int i = 0; i < N; i++) graph[i] = new ArrayList<>();
        for(int i = 0; i < M; i++) {
            int a = scanner.nextInt()-1;
            int b = scanner.nextInt()-1;
            graph[a].add(dist(a,b,N));
            graph[b].add(dist(b,a,N));
        }
        for(int i = 0; i < N; i++) Collections.sort(graph[i]);
        outer:
        for(int i = 1; i*i <= N; i++) {
            if (N%i != 0) continue;
            boolean good = i != 1;
            top:
            for(int j = 0; j < N && good; j++) {
                if (graph[j].size() != graph[pos(j, N/i, N)].size()) {
                    good = false;
                    continue top;
                }
                for(int k = 0; k < graph[j].size(); k++) {
                    if ((int) graph[j].get(k) != (int) graph[pos(j,N/i,N)].get(k)) {
                        good = false;
                        continue  top;
                    }
                }
            }
            if (good) {
                out.println("Yes");
                out.flush();
                return;
            }
            for(int j = 0;j < N; j++) {
                if (graph[j].size() != graph[pos(j, i, N)].size()) continue outer;
                for(int k = 0; k < graph[j].size(); k++) {
                    if ((int)graph[j].get(k) != (int)graph[pos(j, i, N)].get(k)) continue outer;
                }
            }
            out.println("Yes");
            out.flush();
            return;
        }
        out.println("No");
        out.flush();
    }
    //dist from a -> b
    public static int dist(int a, int b, int N) {
        if (b < a) return b + N - a;
        else return b - a;
    }
    public static int pos(int a, int b, int N) {
        return (a - b + N) % N;
    }
    
//    public static class Point {
//        long x, y;
//        public Point(long xx, long yy) {
//            x = xx; y = yy;
//        }
//    }
    
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
        
        double nextDouble() {
            return Double.parseDouble(next());
        }
        
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        
        int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int idx = 0; idx < n; idx++) {
                a[idx] = nextInt();
            }
            return a;
        }
    }
}
