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.lang.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public boolean help(TreeSet<Integer>[] seg,ArrayList<Integer> l,int[] pf,int value,int counter,int n) {
        if(counter==l.size()) {
            if(value==n) {
                return false;
            }
            return this.help1(value, seg, n);
        }
        boolean ret=false;
        for(int i=0;i<=pf[l.get(counter)];i++) {
            ret|=this.help(seg,l, pf, (int)(value*Math.pow(l.get(counter),i)), counter+1,n);
        }
        return ret;
    }
    public boolean help1(int value,TreeSet<Integer>[] seg,int n) {
        int flag=1;
        for(int i=0;i<n;i++) {
            for(int j:seg[i]) {
                int f=(i+value)%n;
                int s=(j+value)%n;
                if(!seg[Math.min(f, s)].contains(Math.max(f, s))){
                    flag=0;
                    break;
                }
            }
            if(flag==0) {
                break;
            }
        }
        if(flag==0) {
            //System.out.println(value);
            return false;
        }
        else {
            //System.out.println(value);
            return true;
        }
    }
    public static void main(String[] args) throws Exception{
        // TODO Auto-generated method stub
        Reader.init(System.in);
        Main mm=new Main();
        int n=Reader.nextInt();
        int m=Reader.nextInt();
        int[] arr=new int[n];
        int[] primes=new int[n+1];
        int[] pf=new int[n+1];
        int temp=n;
        TreeSet<Integer> list=new TreeSet<Integer>();
        for(int i=2;i<=n;i++) {
            if(primes[i]==0) {
                primes[i]=1;
                int counter=2;
                while(counter*i<=n) {
                    primes[counter*i]=1;
                    counter++;
                }
                while(temp%i==0) {
                    temp/=i;
                    pf[i]++;
                    list.add(i);
                }
            }
        }
        ArrayList l=new ArrayList<Integer>(list);
        TreeSet<Integer>[] seg=new TreeSet[n];
        for(int i=0;i<n;i++) {
            seg[i]=new TreeSet<Integer>();
        }
        for(int i=0;i<m;i++) {
            int f=Reader.nextInt()-1;
            int s=Reader.nextInt()-1;
            seg[Math.min(f, s)].add(Math.max(f, s));
        }
        if(mm.help(seg, l, pf, 1, 0, n)) {
            System.out.println("Yes");
        }
        else {
            System.out.println("No");
        }
}
}
class pair{
        int f;
        int s;
        pair(int f,int s){
            this.f=f;
            this.s=s;
        }
        
}
class a implements Comparator<pair>{
        public int compare(pair n1,pair n2) {
            return n1.s-n2.s;
        }
}

class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                     new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }

    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                   reader.readLine() );
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    static long nextLong() throws IOException {
        return Long.parseLong(next());
    }
    
    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
}