Codeforces Round 562 (Div. 2) |
---|
Закончено |
У жабы Ивана есть $$$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$$$-й паре.
Выведите «YES», если существуют два таких целых числа $$$x$$$ и $$$y$$$ ($$$1 \leq x < y \leq n$$$), что в каждой данной паре хотя бы одно число равно $$$x$$$ или $$$y$$$. Иначе выведите «NO». Вы можете выводить каждую букву в любом регистре (верхнем или нижнем).
4 6 1 2 1 3 1 4 2 3 2 4 3 4
NO
5 4 1 2 2 3 3 4 4 5
YES
300000 5 1 2 1 2 1 2 1 2 1 2
YES
В первом примере вы не можете выбрать подходящие $$$x$$$, $$$y$$$, потому что для каждой такой пары вы можете найти пару, которая их не содержит.
Во втором примере вы можете выбрать $$$x=2$$$ и $$$y=4$$$.
В третьем примере вы можете выбрать $$$x=1$$$ и $$$y=2$$$.
Название |
---|