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.*;
import java.util.*;
 
 
public class Main {
     static ArrayList a[]=new ArrayList[3000001];
     static boolean visited[]=new boolean [300001];
     static Vector<Long>v=new Vector<>();
     static long  pre[]=new long[500001];
     static long dp[]=new long[500001];
     static long mod=(long)1e9+7;
     static long f(int i,int j) {
    	return (((pre[j]-pre[i-1]+mod)%mod*modInverse(dp[i-1],mod))%mod);
     }
     static void cal() {
    	 dp[0]=1L;
    	 for(int i=1;i<500001;i++) {
    		 dp[i]=(dp[i-1]*29L)%mod;
    	 }
    	 for(int i=1;i<=v.size();i++) {
    		  pre[i]=(pre[i-1]+(dp[i]*v.get(i-1))%mod)%mod;
    	 }
     }
     public static void main(String[]args)
    {
        InputReader in=new InputReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n=in.nextInt();
        int m=in.nextInt();
        for(int i=0;i<=n;i++) {
        	a[i]=new ArrayList<pair>();
        }
        for(int i=0;i<m;i++) {
        	int x=in.nextInt();
        	int y=in.nextInt();
        	a[x].add(new pair((x<y)?(y-x):(n-x+y),y));
        	a[y].add(new pair((x>y)?(x-y):(n-y+x),x));
        }
        int start[]=new int[n+1];
        int end[]=new  int[n+1];
        for(int i=1;i<=n;i++) {
        	Collections.sort(a[i]);
        	start[i]=v.size()+1;
        	for(int j=0;j<a[i].size();j++) {
        		pair id=(pair) a[i].get(j);
        		v.add(id.x);
        	}
        	end[i]=v.size();
        	
        }
        cal();
        boolean ans=false;
        for(int i=2;i*i<=n;i++) {
        	if(n%i==0) {
        		long val=f(start[1],end[i]);
        		boolean chk=true;
        		for(int j=1;j<n;j+=i) {
        			long val1=f(start[j],end[i+j-1]);
        			chk&=(val1==val);
        		}
        		ans|=chk;
        		val=f(start[1],end[n/i]);
        		chk=true;
        		for(int j=1;j<n;j+=n/i) {
        			long val1=f(start[j],end[n/i+j-1]);
        			chk&=(val1==val);
        		}
        		ans|=chk;
        	}
        }
       boolean chk=true;
        long val=f(start[1],end[1]);
		for(int j=1;j<n;j++) {
			long val1=f(start[j],end[1+j-1]);
			chk&=(val1==val);
		}
		ans|=chk;
        if(ans)
        	pw.println("Yes");
        else
        	pw.println("No");
        pw.flush();
        pw.close();
 
    }
    private static void debug(Object... o) {
        System.out.println(Arrays.deepToString(o));
    }
   static class InputReader 
        {
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;
 
        public InputReader(InputStream stream) 
        { 
            this.stream = stream;
        }
        public int snext() 
        {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) 
            {
                curChar = 0;
                try 
                {
                    snumChars = stream.read(buf);
                } 
                
                catch (IOException e) 
                {
                    throw new InputMismatchException();
                }
                
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
 
        public int nextInt() 
        {
            int c = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = snext();
            }
            int res = 0;
            do 
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public long nextLong()
        {
            int c = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            int sgn = 1;
            if (c == '-') 
            {
                sgn = -1;
                c = snext();
            }
            long res = 0;
            do 
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public int[] nextIntArray(int n) 
        {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) 
            {
                a[i] = nextInt();
            }
            return a;
        }
        static class tri implements Comparable<tri> {
            int p, c, l;
 
            tri(int p, int c, int l) {
                this.p = p;
                this.c = c;
                this.l = l;
            }
 
            public int compareTo(tri o) {
                return Integer.compare(l, o.l);
            }
        }
 
        public String readString()
        {
            int c = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = snext();
            } while (!isSpaceChar(c));
            return res.toString();
        }
 
        public String nextLine() 
        {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = snext();
            } while (!isEndOfLine(c));
            return res.toString();
        }
 
        public boolean isSpaceChar(int c) 
        {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
 
        private boolean isEndOfLine(int c) 
        {
            return c == '\n' || c == '\r' || c == -1;
        }
 
        public interface SpaceCharFilter
        {
            public boolean isSpaceChar(int ch);
        }
    }
   public static long modularExponentiation(long x,long n,long M)
   {
       long result=1;
       while(n>0)
       {
           if(n % 2 ==1)
               result=(result%M * x%M)%M;
           x=(x%M * x%M)%M;
           n=n/2;
       }
       return result;
   }
   
   public static long modInverse(int A,int M)
   {
       return modularExponentiation(A,M-2,M);
   }
   
   public static long modInverse(long A,long M)
   {
       return modularExponentiation(A,M-2,M);
   }
    static class pair implements Comparable<pair>{
        Long x;
        Long y;

        pair(long x2,long l){
            this.x=x2;
            this.y=l;
        }
        
        public int compareTo(pair o) {
                int result = x.compareTo(o.x);
                if(result==0)
                    result = y.compareTo(o.y);
                
            return result;
            }  
         public String toString(){
            return (x+" "+y);
        }
  }
    public static long GCD(long a,long b)
    {
        if(b==0)
            return a;
        else
            return GCD(b,a%b);
    }
    public static long[] shuffle(long[] a, Random gen){ 
        for(int i = 0, n = a.length;i < n;i++){ 
            int ind = gen.nextInt(n-i)+i; 
            long d = a[i]; 
            a[i] = a[ind]; 
            a[ind] = d; 
        } 
        return a; 
    }
  static class query{
      Integer x;
      Integer y;
      Long z;
      query(int x,int y,long z){
          this.x=x;
          this.y=y;
          this.z=z;
      }
      
	public String toString() {
    	  return ((x+" "+y+" "+z));
      }
  }
    
}
 