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

import static java.lang.Math.max;
import static java.lang.Math.min;

public class TaskD {
    class Pair {
        public int a,b;
        @Override
        public boolean equals(Object o){
            if(! (o instanceof Pair)){
                return false;
            }
            Pair po = (Pair)o;
            return a==po.a && b==po.b;
        }

        @Override
        public int hashCode(){
            return a*a + b*b;
        }

        public Pair(int aa, int bb) {a=aa; b=bb;}
    }


    int n,m;
    int[][] ps;
    Set<Pair> st;

    ArrayList<Integer> getDivisors(int a){
        ArrayList<Integer> res = new ArrayList<>();
        for(int i=1; i<a; i++){
            if(a % i == 0){
                res.add(i);
            }
        }
        return res;
    }

    boolean check(int k){
        for(int i=0; i<m; i++){
            int a = ps[i][0], b = ps[i][1];
            int aa = (a + k)%n, bb = (b + k)%n;
            if(aa==0) aa=n; if(bb==0) bb = n;
            Pair p = new Pair(min(aa,bb), max(aa,bb));
            //System.out.println(k + " " + aa + " " + bb);
            if(!st.contains(p)) return false;
        }
        return true;
    }

    public void solve() throws Exception{
        st = new HashSet<>();
        Scanner sc = new Scanner(System.in);
        //Scanner sc = new Scanner(new FileInputStream("inputs/d.in"));
        n = sc.nextInt(); m = sc.nextInt();
        ps = new int[m][2];
        for(int i=0; i<m; i++){
            int a, b;
            a = sc.nextInt(); b = sc.nextInt();
            ps[i][0] = min(a,b); ps[i][1] = max(a, b);
            st.add(new Pair(ps[i][0], ps[i][1]));
        }

        //System.out.println(st.contains(new Pair(5,7)));
        Arrays.sort(ps, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        ArrayList<Integer> ds = getDivisors(n);
        boolean f = false;
        for(Integer k : ds){
            if(check(k)){
                f = true; break;
            }
        }

        if(f) System.out.println("Yes");
        else System.out.println("No");

    }
    public static void main(String[] args) throws Exception {
        TaskD s = new TaskD();
        s.solve();
    }
}

