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 A
{
      public static void main(String ar[]) throws Exception
      {
            BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
            String s1[]=br.readLine().split(" ");
            int n=Integer.parseInt(s1[0]);
            int m=Integer.parseInt(s1[1]);
            int a[]=new int[m];
            int b[]=new int[m];
            boolean cc=true;
            HashMap<Integer,Integer> hs=new HashMap<Integer,Integer>();
            for(int i=0;i<m;i++)
            {
                  String s2[]=br.readLine().split(" ");
                  a[i]=Integer.parseInt(s2[0]);
                  b[i]=Integer.parseInt(s2[1]);
                  if(hs.containsKey(a[i]))
                   hs.put(a[i],1+hs.get(a[i]));
                  else
                   hs.put(a[i],1);
                   
                  if(hs.containsKey(b[i]))
                   hs.put(b[i],1+hs.get(b[i]));
                  else
                   hs.put(b[i],1);
            }
            
            HashSet<Integer> h=new HashSet<Integer>();
            for(int i=0;i<m;i++)
            {
                  if(hs.get(a[i])>=m/2+m%2)
                   h.add(a[i]);
                  if(hs.get(b[i])>=m/2+m%2)
                   h.add(b[i]);
            }
            
            ArrayList<Integer> al=new ArrayList<Integer>();
             
            for(int i:h)
             al.add(i);
            
            
            for(int i=0;i<al.size();i++)
            {
                  int val1=-1,val2=-1;
                  for(int j=0;j<m;j++)
                  {
                        if(a[j]!=al.get(i))
                        { val1=a[j];  val2=a[j];  break; }
                        else if(b[j]!=al.get(i))
                        { val1=b[j];  val2=b[j];  break; }
                  }
                  boolean u1=true,u2=true;
                  for(int j=0;j<m;j++)
                  {
                        if(a[j]!=al.get(i) && b[j]!=al.get(i))
                        { val1=a[j];  val2=b[j]; break; }
                  }
                  
                  for(int j=0;j<m;j++)
                  {
                        if(a[j]!=al.get(i) && b[j]!=al.get(i) && a[j]!=val1 && b[j]!=val1)
                         u1=false;
                  }
                  
                  for(int j=0;j<m;j++)
                  {
                        if(a[j]!=al.get(i) && b[j]!=al.get(i) && a[j]!=val2 && b[j]!=val2)
                         u2=false;
                  }
                  
                  if((u1 && val1!=-1 ) || (u2 && val2!=-1))
                  { System.out.println("YES"); cc=false; break; }
            }
            
            if(cc)
             System.out.println("NO");
      }
}