链接：https://codeforces.com/problemset/problem/1169/B

Toad Ivan has mm pairs of integers, each integer is between 11 and nn, inclusive. The pairs are (a1,b1),(a2,b2),…,(am,bm)(a1,b1),(a2,b2),…,(am,bm).

He asks you to check if there exist two integers xx and yy (1≤x<y≤n1≤x<y≤n) such that in each given pair at least one integer is equal to xx&nbs***bsp;yy.

Input

The first line contains two space-separated integers nn and mm (2≤n≤3000002≤n≤300000, 1≤m≤3000001≤m≤300000) — the upper bound on the values of integers in the pairs, and the number of given pairs.

The next mm lines contain two integers each, the ii-th of them contains two space-separated integers aiai and bibi (1≤ai,bi≤n,ai≠bi1≤ai,bi≤n,ai≠bi) — the integers in the ii-th pair.

Output

Output "YES" if there exist two integers xx and yy (1≤x<y≤n1≤x<y≤n) such that in each given pair at least one integer is equal to xx&nbs***bsp;yy. Otherwise, print "NO". You can print each letter in any case (upper or lower).

Examples

input

Copy

4 6
1 2
1 3
1 4
2 3
2 4
3 4

output

Copy

NO

input

Copy

5 4
1 2
2 3
3 4
4 5

output

Copy

YES

input

Copy

300000 5
1 2
1 2
1 2
1 2
1 2

output

Copy

YES

Note

In the first example, you can't choose any xx, yy because for each such pair you can find a given pair where both numbers are different from chosen integers.

In the second example, you can choose x=2x=2 and y=4y=4.

In the third example, you can choose x=1x=1 and y=2y=2.

代码：

#include <bits/stdc++.h>
using namespace std;
long long t,n,m,k,s=0,x,y,p,q,max1=0,c,d;
long long a[1000001],b[1000001],vis[1000001]={0};
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i]>>b[i];
	}
	x=a[1],y=b[1];
	int fl=0;
	for(int i=2;i<=m;i++)
	{
		if(a[i]!=x&&b[i]!=y&&a[i]!=y&&b[i]!=x)
		{
			p=a[i];
			q=b[i];
			fl=1;
			break;
		}
	}
	if(fl==1)
	c=x,d=p;
	else
	{
		cout<<"YES";
		return 0;
	}
	
	
	int flag=0;
	for(int i=1;i<=m;i++)
	{
		if(a[i]==c||b[i]==c||a[i]==d||b[i]==d)
		{
			continue;
		}
		else
		{
			flag=1;
			break;
		}
	}
	if(flag==0)
	cout<<"YES";
	else
	{
		c=x,d=q;
		flag=0;
		for(int i=1;i<=m;i++)
		{
			if(a[i]==c||b[i]==c||a[i]==d||b[i]==d)
			{
				continue;
			}
			else
			{
				flag=1;
				break;
			}
		}
		if(flag==0)
		cout<<"YES";
		else
		{
			c=y,d=q;
			flag=0;
			for(int i=1;i<=m;i++)
			{
				if(a[i]==c||b[i]==c||a[i]==d||b[i]==d)
				{
					continue;
				}
				else
				{
					flag=1;
					break;
				}
			}
			if(flag==0)
			cout<<"YES";
			else
			{
				c=y,d=p;
				flag=0;
				for(int i=1;i<=m;i++)
				{
					if(a[i]==c||b[i]==c||a[i]==d||b[i]==d)
					{
						continue;
					}
					else
					{
						flag=1;
						break;
					}
				}
				if(flag==0)
				cout<<"YES";
				else
				cout<<"NO";
			}
		}
	}
}