A - Shuttle Bus

Alex is a driver of a shuttle bus whose working duty is to drive around Byteland and let the tourists do sightseeing there.

The territory of Byteland is strange which can be represent by an grid with exactly 2 rows and N columns. There are M churches on some cells in Byteland where sightseeing there are forbidden. On the other hand, there is an attraction in each of the remaining cells.

On each day, Alex drives the shuttle bus from the frontier of Byteland, which is the top-left corner of the 2 × N grid. The shuttle bus can travel from one cell to its adjacent cells which have a common side with it each time. Alex will drive the shuttle bus to visit all attractions. Undoubtedly, he cannot drive into the cells where the churches are located.

Alex does not want to make his tourists bored, so he hopes to visit all attractions, except the churches, exactly once. The tour can end in any cell. Given the length of the grid and the positions of the churches, determine whether Alex can do so successfully.

Input

The first line of contains 2 integers N, M, representing the length of the grid of Byteland and the number of churches there. (1 ≤ N ≤ 109, 1 ≤ M ≤ 5000)

The following M lines contains 2 integers ri, ci, representing the position of the ith church. (1 ≤ ri ≤ 2, 1 ≤ ci ≤ N)

The positions of the churches are distinct and no church will be located at the top-left corner of the grid.

Output

Please output Yes if Alex can visit all attractions except the churches exactly once and output No otherwise.

Examples

Input

5 3
2 1
1 3
2 5

Output

Yes

Input

3 2
2 1
2 3

Output

No

Input

3 2
1 2
2 2

Output

No

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 5010
using namespace std;
struct node
{
	int x,y;
}c[N];
int n,m;

bool cmp(node a,node b)
{
	return a.x<b.x;
}

void init()
{
	for(int i=0;i<m;i++)
	{
		c[i].x=0;
		c[i].y=0;
	}
}

int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(int i=0;i<m;i++)
			scanf("%d%d",&c[i].y,&c[i].x);
		sort(c,c+m,cmp);
		bool flag=true;
		if(c[0].x%2==0&&c[0].y==2) flag=false;
		if(c[0].x%2==1&&c[0].y==1) flag=false;
		//第一个church的位置 
		if(flag)
		{
			for(int i=m-1;i>=1;)
			{
				//此时判断的是最后的church 
				if(c[i-1].x==c[i].x&&c[i].x==n)
					n--,i-=2,m-=2;
				//如果最后一行都为church这并不影响走完每个景点 
				else if(c[i-1].x==c[i].x&&c[i].x!=n)
				{
					flag=false;break;
				}
				else i--;
			}
		}
			
		if(flag)
		//判断过程中的两种情况 
		{
			for(int i=1;i<m;i++)
			{
				if(c[i-1].y==c[i].y&&(c[i].x-c[i-1].x)%2==0)
					{
						flag=false;break;
					}
				else if(c[i-1].y!=c[i].y&&(c[i].x-c[i-1].x)%2==1)
					{
						flag=false;break;
					}
			}
		}
			
		if(flag) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}