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.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Hashtable;

public class B {
	public static void main(String[] args) throws IOException {
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		
		String[] firstLine = input.readLine().split(" ");
		
		int n = Integer.parseInt(firstLine[0]);
		int m = Integer.parseInt(firstLine[1]);
		
		Point[] pairs = new Point[m];
		
		for (int i = 0; i < m; i++) {
			String[] nextLine = input.readLine().split(" ");
			pairs[i] = new Point(Integer.parseInt(nextLine[0]), Integer.parseInt(nextLine[1]));
		}
		
		Hashtable<Integer, Integer> occurrenceCount = new Hashtable<Integer, Integer>();
		HashSet<Integer> candidates = new HashSet<Integer>();
		
		for (int i = 0; i < pairs.length; i++) {
			int count = occurrenceCount.getOrDefault(pairs[i].x, 0);
			occurrenceCount.put(pairs[i].x, count + 1);
			if (count + 1 >= pairs.length / 2) {
				candidates.add(pairs[i].x);
			}
			
			if (pairs[i].y != pairs[i].x) {
				count = occurrenceCount.getOrDefault(pairs[i].y, 0);
				occurrenceCount.put(pairs[i].y, count + 1);
				if (count + 1 >= pairs.length / 2) {
					candidates.add(pairs[i].y);
				}
			}
		}
		
		boolean found = false;
		
		for (Integer candidate: candidates) {
			int candidateCount = occurrenceCount.get(candidate);
			if (candidateCount >= pairs.length) {
				found = true;
				break;
			}
			Hashtable<Integer, Integer> occurrenceCount2 = new Hashtable<Integer, Integer>();
			
			for (int i = 0; i < pairs.length; i++) {
				if (pairs[i].x == candidate || pairs[i].y == candidate) {
					
				} else {
					int count = occurrenceCount2.getOrDefault(pairs[i].x, 0);
					occurrenceCount2.put(pairs[i].x, count + 1);
					if (count + 1 >= pairs.length - candidateCount) {
						found = true;
					}
					
					if (pairs[i].y != pairs[i].x) {
						count = occurrenceCount2.getOrDefault(pairs[i].y, 0);
						occurrenceCount2.put(pairs[i].y, count + 1);
						if (count + 1 >= pairs.length - candidateCount) {
							found = true;
						}
					}
				}
			}
		}
		
		if (found) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}
