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.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.logging.Level;
import java.util.logging.Logger;
import java.util.regex.*;

public class Solution implements Runnable{
    
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        InputReader ir = new InputReader(System.in);
         new Thread(null, new Solution(bw,ir), "whatever", 1<<26).start();
    }
    
    public void run() {
       int n = ir.nextInt();
       int m = ir.nextInt();
       long mult = 1000000000;
       HashSet<Long> map = new HashSet<>();
       for (int i = 0; i < m; ++i){
           int p1 = ir.nextInt();
           int p2 = ir.nextInt();
           int minp = Math.min(p1,p2);
           int maxp = Math.max(p1,p2);
           long seg = mult * minp;
           seg += maxp;
           map.add(seg);
           seg = mult * maxp;
           seg += minp;
           map.add(seg);
       }
       HashSet<Integer> divSet = new HashSet<>();
       for (int i = 1; i <= n/2; ++i){
           if (n%i == 0)
               divSet.add(i);
       }
       for (Integer div : divSet){
           boolean found = true;
           for (Long seg : map){
               int from = (int)(seg/mult);
               int to = (int)(seg%mult);
               from += div;
               from %= n;
               if (from == 0)
                   from = n;
               to += div;
               to %= n;
               if (to == 0)
                   to = n;
               long tohaveSeg = mult * from;
               tohaveSeg += to;
               if (!map.contains(tohaveSeg)){
                   found = false;
                   break;
               }
           }
           if (found){
               System.out.println("Yes");
               return;
           }
       }
       System.out.println("No");
    }
    
    public class Segment{
        int from;
        int to;
        public Segment(int from, int to){
            this.from = from;
            this.to = to;
        }
    }
    
    BufferedWriter bw;
    InputReader ir;
    
    public Solution(BufferedWriter bw, InputReader ir) throws IOException {
        this.bw = bw;
        this.ir = ir;
    }

    static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}