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 javafx.util.Pair;
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class Main implements Runnable
{
    boolean multiple = false;
    long MOD = 1000000007;

    @SuppressWarnings("Duplicates")
    void solve() throws Exception
    {
        int n = sc.nextInt();
        int m = sc.nextInt();
        /*builds g with n vertices and m edges*/ TreeMap<Integer, TreeSet<Integer>> g = new TreeMap<>(); for (int I = 0; I < n; I++) g.put(I, new TreeSet<>()); for (int I = 0; I < m; I++) { int u = sc.nextInt() - 1, v = sc.nextInt() - 1; g.get(u).add(v); g.get(v).add(u); }

        boolean reallyGay = false;

        for (int divisor = 1; divisor * divisor <= n; divisor++)
        {
            if (n % divisor != 0) continue;
            int shift = n / divisor;
            boolean gay = true;
            for (int i = 0; i < 1; i++)
            {
                if (shift == n)
                {
                    gay = false;
                    break;
                }
                outer: for (Integer u : g.keySet())
                    for (Integer v : g.get(u))
                        if (!g.get((u + shift) % n).contains((v + shift) % n))
                        {
                            gay = false;
                            break outer;
                        }
                if (gay)
                {
                    reallyGay = true;
                    break;
                }

            }

            gay = true;
            shift = divisor;
            outer: for (Integer u : g.keySet())
                for (Integer v : g.get(u))
                    if (!g.get((u + shift) % n).contains((v + shift) % n))
                    {
                        gay = false;
                        break outer;
                    }

            if (gay)
            {
                reallyGay = true;
                break;
            }
        }
        System.out.println((reallyGay) ? "Yes" : "No");
    }

    long lcm(long a, long b) { return (a / gcd(a, b)) * b; }
    long gcd(long a, long b) { return a == 0 ? b : gcd(b % a, a); }

    /*I/O, and other boilerplate*/ @Override public void run() { try { in = new BufferedReader(new InputStreamReader(System.in));out = new PrintWriter(System.out);sc = new FastScanner(in);if (multiple) { int q = sc.nextInt();for (int i = 0; i < q; i++) solve(); } else solve(); } catch (Throwable uncaught) { Main.uncaught = uncaught; } finally { out.close(); }} public static void main(String[] args) throws Throwable{ Thread thread = new Thread(null, new Main(), "", (1 << 26));thread.start();thread.join();if (Main.uncaught != null) {throw Main.uncaught;} } static Throwable uncaught; BufferedReader in; FastScanner sc; PrintWriter out; } class FastScanner { BufferedReader in; StringTokenizer st; public FastScanner(BufferedReader in) {this.in = in;}public String nextToken() throws Exception { while (st == null || !st.hasMoreTokens()) { st = new StringTokenizer(in.readLine()); }return st.nextToken(); }public int nextInt() throws Exception { return Integer.parseInt(nextToken()); }public long nextLong() throws Exception { return Long.parseLong(nextToken()); }public double nextDouble() throws Exception { return Double.parseDouble(nextToken()); }
}