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 mymy
{

	static OutputStream outputStream = System.out;
	static PrintWriter out = new PrintWriter(outputStream);	

	static class node implements Comparable<node>
		{
			int l;int r;
	
			node(int i,int o)
			{
				l=i;r=o;
			}
			public int compareTo(node n)
			{
				if(this.l!=n.l) return this.l-n.l;
				return this.r-n.r;
			}
		}

	static node[] arr;

	static int m;

	static boolean check(node n)
	{
		int l=n.l,r=n.r;
		int low=0,high=m-1;

		while(low<=high)
		{
			int mid=(low+high)/2;

			if(arr[mid].l==l)
			{
				if(arr[mid].r==r) return true;
				if(arr[mid].r>r) high=mid-1;
				else low=mid+1;
			}
			else if(arr[mid].l>l) high=mid-1;
			else low=mid+1;
		}


		return false;

	}


	public static void main(String[] Atul)throws IOException
	{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

		// int n=Integer.parseInt(br.readLine());

		String[] s=br.readLine().split(" ");

		int n=Integer.parseInt(s[0]);m=Integer.parseInt(s[1]);

		arr=new node[m];

		int[] l=new int[m],r=new int[m];

		for(int i=0;i<m;i++)
		{
			s=br.readLine().split(" ");
			l[i]=Integer.parseInt(s[0])-1;
			r[i]=Integer.parseInt(s[1])-1;
			arr[i]=(new node(Math.min(l[i],r[i]) , Math.max(l[i],r[i])));
			if(r[i]<l[i])
			{
				int t=l[i];
				l[i]=r[i];
				r[i]=t;
			}
		}

		Arrays.sort(arr);

		ArrayList<Integer> a=new ArrayList<Integer>();

		int i=2;

		a.add(1);

		while(i*i<n)
		{
			if(n%i==0)
			{
				a.add(i);
				a.add(n/i);
			}
			i++;
		}
		if(i*i==n) a.add(i);

		Collections.sort(a);

		String ans="No";

		for(i=a.size()-1;i>=0;i--)
		{
			int now=a.get(i);

			int flg=1;

			for(int j=0;j<m;j++)
			{				
				if(!check(new node( Math.min((l[j]+now)%n,(r[j]+now)%n) , Math.max((l[j]+now)%n,(r[j]+now)%n)  )))
					{flg=0;break;}
			}
			if(flg==1)
			{
				ans="Yes";
				break;
			}
		}

		out.println(ans);
		out.close();

	}
}
