← 返回题目列表

Codeforces · 1169/B

B. 对

中文机器翻译题面 查看原题

Toad Ivan 有 $$$m$$$ 个整数对,每个整数在 $$$1$$$ 和 $$$n$$$ 之间(含)。这些对是 $$$(a_1, b_1), (a_2, b_2), \ldots, (a_m, b_m)$$$。

他要求你检查是否存在两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \leq x < y \leq n$$$),使得在每个给定的对中至少有一个整数等于 $$$x$$$ 或 $$$y$$$。

输入

第一行包含两个空格分隔的整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 300\,000$$$, $$$1 \leq m \leq 300\,000$$$) - 对中整数值的上限以及给定对的数量。

接下来的 $$$m$$$ 行每行包含两个整数,其中第 $$$i$$$ 包含两个空格分隔的整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n, a_i \neq b_i$$$) - 第 $$$i$$$ 中的整数对。

输出

如果存在两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \leq x < y \leq n$$$),则输出“YES”,使得在每个给定对中至少有一个整数等于 $$$x$$$ 或 $$$y$$$。否则,打印“NO”。您可以以任何大小写(大写或小写)打印每个字母。

示例

输入 #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

注意

在第一个示例中,您不能选择任何 $$$x$$$、$$$y$$$,因为对于每个这样的对,您都可以找到给定的对,其中两个数字都不同于所选整数。

在第二个示例中,您可以选择 $$$x=2$$$ 和 $$$y=4$$$。

在第三个示例中,您可以选择 $$$x=1$$$ 和 $$$y=2$$$。