Рассмотрим $$$n$$$ вышек связи, пронумерованных от $$$1$$$ до $$$n$$$. Они соединены $$$m$$$ двунаправленными проводами. У каждой вышки есть определенный набор частот, которые она принимает, $$$i$$$-я из них принимает частоты от $$$l_i$$$ до $$$r_i$$$.
Скажем, что вышка $$$b$$$ доступна из вышки $$$a$$$, если существует такая частота $$$x$$$ и последовательность вышек $$$a=v_1, v_2, \dots, v_k=b$$$, что соседние вышки в последовательности напрямую соединены проводом, и каждая из них принимает частоту $$$x$$$. Обратите внимание, что доступность не является транзитивной, т.е. если $$$b$$$ доступна из $$$a$$$, а $$$c$$$ доступна из $$$b$$$, $$$c$$$ может быть недоступна из $$$a$$$.
Ваша задача — определить номера вышек связи, доступных из $$$1$$$-й вышки.
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$0 \le m \le 4 \cdot 10^5$$$) — количество вышек связи и количество проводов соответственно.
Затем следует $$$n$$$ строк, $$$i$$$-я из них содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le 2 \cdot 10^5$$$) — границы допустимых частот для $$$i$$$-й вышки.
Затем следует $$$m$$$ строк, $$$i$$$-я из них содержит два целых числа $$$v_i$$$ и $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$; $$$v_i \ne u_i$$$) — $$$i$$$-й провод, соединяющий вышки $$$v_i$$$ и $$$u_i$$$. Нет двух проводов, соединяющих одну и ту же пару вышек.
В единственную строку выведите различные целые числа от $$$1$$$ до $$$n$$$ в порядке возрастания — номера вышек связи, доступных из $$$1$$$-й вышки.
6 5 3 5 1 2 2 4 2 3 3 3 4 6 1 3 6 1 3 5 3 6 2 3
1 3 5 6
3 1 2 3 1 4 1 1 1 3
1
5 5 1 3 2 3 2 2 3 5 2 4 1 2 2 3 3 4 4 1 4 5
1 2 3 4 5
Название |
---|