Problem F

Statement
Copy Copied
Description:
There are $$$n$$$ communication towers, numbered from $$$1$$$ to $$$n$$$, and $$$m$$$ bidirectional wires between them. Each tower has a certain set of frequencies that it accepts, the $$$i$$$-th of them accepts frequencies from $$$l_i$$$ to $$$r_i$$$.

Let's say that a tower $$$b$$$ is accessible from a tower $$$a$$$, if there exists a frequency $$$x$$$ and a sequence of towers $$$a=v_1, v_2, \dots, v_k=b$$$, where consecutive towers in the sequence are directly connected by a wire, and each of them accepts frequency $$$x$$$. Note that accessibility is not transitive, i. e if $$$b$$$ is accessible from $$$a$$$ and $$$c$$$ is accessible from $$$b$$$, then $$$c$$$ may not be accessible from $$$a$$$.

Your task is to determine the towers that are accessible from the $$$1$$$-st tower.

Input Format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$0 \le m \le 4 \cdot 10^5$$$) — the number of communication towers and the number of wires, respectively.

Then $$$n$$$ lines follows, the $$$i$$$-th of them contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le 2 \cdot 10^5$$$) — the boundaries of the acceptable frequencies for the $$$i$$$-th tower.

Then $$$m$$$ lines follows, the $$$i$$$-th of them contains two integers $$$v_i$$$ and $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$; $$$v_i \ne u_i$$$) — the $$$i$$$-th wire that connects towers $$$v_i$$$ and $$$u_i$$$. There are no two wires connecting the same pair of towers.

Output Format:
In a single line, print distinct integers from $$$1$$$ to $$$n$$$ in ascending order — the indices of the communication towers that are accessible from the $$$1$$$-st tower.

Note:
None