Pairs

题意翻译

给定 $ m $ 个数对$ \ (a_i, \ b_i) \ $ 其中 $ \ a_i, \ b_i $ 是在$ [1, n]$范围的整数 请问是否能找到两个整数$ \ x, y \ (1 \le x < y \le n)$ 使得每一个数对中至少有一个数等于 $ x $ 或 $ y$

题目描述

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), \ldots, (a_m, b_m) $ . He asks you to check if there exist two integers $ x $ and $ y $ ( $ 1 \leq x < y \leq n $ ) such that in each given pair at least one integer is equal to $ x $ or $ y $ .

输入输出格式

输入格式

The first line contains two space-separated integers $ n $ and $ m $ ( $ 2 \leq n \leq 300\,000 $ , $ 1 \leq m \leq 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 \leq a_i, b_i \leq n, a_i \neq b_i $ ) — the integers in the $ i $ -th pair.

输出格式

Output "YES" if there exist two integers $ x $ and $ y $ ( $ 1 \leq x < y \leq 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).

输入输出样例

输入样例 #1

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

输出样例 #1

NO

输入样例 #2

5 4
1 2
2 3
3 4
4 5

输出样例 #2

YES

输入样例 #3

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

输出样例 #3

YES

说明

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 $ .