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 implements Runnable{
    public static void main(String[] args) throws Exception {
        //new Thread(null,new Main(),"Thread-1",1024*1024*10).start();
        new Main().solve();
    }
    ArrayList<Integer>[]x;
    void solve() throws Exception{
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        int n=in.nextInt(),m=in.nextInt();
        x=new ArrayList[n+1];
        for(int i=1;i<=n;i++)x[i]=new ArrayList<>();
        for(int i=0;i<m;i++){
            int a=in.nextInt(),b=in.nextInt();
            if(a>b){
                int tmp=a;a=b;b=tmp;
            }
            x[a].add(b-a);
            x[b].add(a+n-b);
        }
        int[]s=new int[2*n-1];
        int base=1000000007;
        for(int i=1;i<=n;i++){
            Collections.sort(x[i]);
            for(int tmp:x[i])s[i-1]=s[i-1]*base+tmp;
        }
        for(int i=n;i<2*n-1;i++)s[i]=s[i-n];
        if(KMPNext(s,n))out.println("Yes");
        else out.println("No");
        out.flush();
    }
    private static boolean KMPNext(int[] pattern,int n) {
        //next数组为第k个字符匹配失败后可跳过的长度,可跳过的长度为k之前的字符串中前缀与后缀相同的长度
        int next[]=new int[pattern.length];
        int i = 0;
        int j = -1;
        next[0] = -1;
        while (i < next.length - 1) {
            if (j == -1 || pattern[i] == pattern[j]) {
                i++;j++;
                next[i] = j;
                if(pattern[i]==pattern[j]&&next[i]==n-1)return true;
            } else j = next[j];
        }
        return false;
    }
    class Pair{
        int a,b;
        Pair(int x,int y){
            a=x;b=y;
        }
    }
    @Override
    public void run() {
        try {
            solve();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    void shuffle(int[]a,int l,int r){
        Random rnd=new Random();
        for (int i=r; i>l+1; i--) {
            int j=rnd.nextInt(i),tmp=a[j];
            a[j]=a[i-1];
            a[i-1]=tmp;
        }
    }
    void shuffle(Object[]a,int l,int r){
        Random rnd=new Random();
        for (int i=r; i>l+1; i--) {
            int j=rnd.nextInt(i);
            Object tmp=a[j];
            a[j]=a[i-1];
            a[i-1]=tmp;
        }
    }
    void shuffle(long[]a,int l,int r){
        Random rnd=new Random();
        for (int i=r; i>l+1; i--) {
            int j=rnd.nextInt(i);
            long tmp=a[j];
            a[j]=a[i-1];
            a[i-1]=tmp;
        }
    }
    class InputReader{
        StreamTokenizer tokenizer;
        public InputReader(InputStream stream){
            tokenizer=new StreamTokenizer(new BufferedReader(new InputStreamReader(stream)));
            tokenizer.ordinaryChars(33,126);
            tokenizer.wordChars(33,126);
        }
        public String next() throws IOException {
            tokenizer.nextToken();
            return tokenizer.sval;
        }
        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }
        public boolean hasNext() throws IOException {
            int res=tokenizer.nextToken();
            tokenizer.pushBack();
            return res!=tokenizer.TT_EOF;
        }
    }
}