Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

divide and conquer

dsu

*2700

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Communication Towers

time limit per test

4 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputThere 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

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

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.

Examples

Input

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

Output

1 3 5 6

Input

3 1 2 3 1 4 1 1 1 3

Output

1

Input

5 5 1 3 2 3 2 2 3 5 2 4 1 2 2 3 3 4 4 1 4 5

Output

1 2 3 4 5

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 21:37:23 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|