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.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class D {
	static InputReader in = new InputReader(System.in);
	static OutputWriter out = new OutputWriter(System.out);

	public static void main(String[] args) {

		int n = in.nextInt(), m = in.nextInt();
		StringBuilder[] arr = new StringBuilder[n];
		for (int i = 0; i < n; i++)
			arr[i] = new StringBuilder();

//		for (int i = 0; i < n; i++)
//			arr[i].append('0');
			
		for (int i = 0; i < m; i++) {
			int a = in.nextInt() - 1, b = in.nextInt() - 1;
			arr[a].append(Math.max(a, b) - Math.min(a, b));
			arr[a].append(n + Math.min(a, b) - Math.max(a, b));
			arr[b].append(Math.max(a, b) - Math.min(a, b));
			arr[b].append(n + Math.min(a, b) - Math.max(a, b));
		}
		
		for (int i = 0; i < n; i++)
			arr[i].append('0');
		
		for (int i = 0; i < n; i++) {
			char[] c = arr[i].toString().toCharArray();
			Arrays.sort(c);
			arr[i] = new StringBuilder(new String(c));
		}

		StringBuilder text = new StringBuilder();
		for (int i = 1; i < n; i++)
			text.append(arr[i].toString());
		for (int i = 0; i < n - 1; i++)
			text.append(arr[i].toString());
		
		StringBuilder pattern = new StringBuilder();
		for (int i = 0; i < n; i++)
			pattern.append(arr[i].toString());

		int idx = kmpMatcher(text.toString(), pattern.toString());
		if (idx == -1)
			out.println("No");
		else
			out.println("Yes");
		
		out.flush();
	}

	static int[] prefixFunction(String s) {
		int[] p = new int[s.length()];
		int k = 0;
		for (int i = 1; i < s.length(); i++) {
			while (k > 0 && s.charAt(k) != s.charAt(i))
				k = p[k - 1];
			if (s.charAt(k) == s.charAt(i))
				++k;
			p[i] = k;
		}
		return p;
	}

	static int kmpMatcher(String s, String pattern) {
		int m = pattern.length();
		if (m == 0)
			return 0;
		int[] p = prefixFunction(pattern);
		for (int i = 0, k = 0; i < s.length(); i++)
			for (;; k = p[k - 1]) {
				if (pattern.charAt(k) == s.charAt(i)) {
					if (++k == m)
						return i + 1 - m;
					break;
				}
				if (k == 0)
					break;
			}
		return -1;
	}

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

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
		}

		public String nextLine() {
			try {
				return reader.readLine();
			} catch (Exception e) {
				return tokenizer.nextToken();
			}
		}

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

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

		public double nextDouble() {
			return Double.parseDouble(next());
		}

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

		public int[] nextIntArray(int n) {
			int[] array = new int[n];
			for (int i = 0; i < n; i++)
				array[i] = nextInt();
			return array;
		}

		public double[] nextDoubleArray(int n) {
			double[] array = new double[n];
			for (int i = 0; i < n; i++)
				array[i] = nextDouble();
			return array;
		}

		public long[] nextLongArray(int n) {
			long[] array = new long[n];
			for (int i = 0; i < n; i++)
				array[i] = nextLong();
			return array;
		}

	}

	static class OutputWriter {
		private PrintWriter writer;

		public OutputWriter(OutputStream outputStream) {
			writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
		}

		public void print(Object o) {
			writer.print(o.toString());
		}

		public void println(Object o) {
			writer.print(o.toString());
			writer.print('\n');
		}

		public void flush() {
			writer.flush();
		}

	}
}
