Toad Ivan has m pairs of integers, each integer is between 1 and n, inclusive. The pairs are (a_1, b_1), (a_2, b_2), …, (a_m, b_m). 

He asks you to check if there exist two integers x and y (1 ≤ x < y ≤ n) such that in each given pair at least one integer is equal to x or y.

Input

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

The next m lines contain two integers each, the i-th of them contains two space-separated integers a_i and b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i) — the integers in the i-th pair.

Output

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

Examples

Input


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


Output


NO


Input


5 4
1 2
2 3
3 4
4 5


Output


YES


Input


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


Output


YES

Note

In the first example, you can't choose any x, y 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=2 and y=4.

In the third example, you can choose x=1 and y=2.
import java.util.*;
import java.io.*;
public class Main
{
    public static void main(String[] args)throws IOException
    {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(input.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] a = new int[n+1];
        HashMap<String,Integer> map = new HashMap<String,Integer>();
        int p1 = -1;
        int p2 = -1;
        for(int i = 0; i < m; i++)
        {
        	st = new StringTokenizer(input.readLine());
        	int one = Integer.parseInt(st.nextToken());
        	int two = Integer.parseInt(st.nextToken());
        	int temp = Math.min(one,two);
        	two = Math.max(one,two);
        	one = temp;
        	a[one]++;
        	a[two]++;
        	if(!map.containsKey(one+"@"+two)) map.put(one+"@"+two,1);
        	else map.put(one+"@"+two,1+map.get(one+"@"+two));
        	if(i==0)
        	{
        		p1 = one;
        		p2 = two;
        	}
        }
        boolean works = false;
        for(int i = 1; i <= n; i++)
        {
        	int count1 = a[p1] + a[i];
        	int one = Math.min(p1,i);
        	int two = Math.max(p1,i);
        	if(map.containsKey(one+"@"+two)) count1 -= map.get(one+"@"+two);
        	if(count1==m&&p1!=i)
        	{
        		works = true;
        		break;
        	}
        	int count2 = a[p2] + a[i];
        	one = Math.min(p2,i);
        	two = Math.max(p2,i);
        	if(map.containsKey(one+"@"+two)) count2 -= map.get(one+"@"+two);
        	if(count2==m&&p2!=i)
        	{
        		works = true;
        		break;
        	}
        }
        if(works) out.print("YES");
        else out.print("NO");
        out.flush();
        out.close();
    }
}