310318: CF1814F. Communication Towers

F. Communication Towerstime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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

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.

ExamplesInput

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 

题目大意：
有n座通信塔，编号从1到n，以及m条双向电线连接它们。每座塔接受一定范围的频率，第i座塔接受的频率从l_i到r_i。如果存在一个频率x和一系列塔a=v_1, v_2, …, v_k=b，其中连续的塔之间通过电线直接连接，并且每座塔都接受频率x，则称塔b从塔a是可访问的。注意，可访问性不是传递的，即如果b从a可访问且c从b可访问，则c不一定从a可访问。任务是确定从第1座塔可访问的塔。

输入数据格式：
第一行包含两个整数n和m（1≤n≤2×10^5；0≤m≤4×10^5）——通信塔的数量和电线的数量。
然后是n行，第i行包含两个整数l_i和r_i（1≤l_i≤r_i≤2×10^5）——第i座塔可接受频率的边界。
然后是m行，第i行包含两个整数v_i和u_i（1≤v_i,u_i≤n；v_i≠u_i）——第i条电线连接的塔v_i和u_i。没有两条电线连接同一对塔。

输出数据格式：
在一行中，按升序打印从1到n的不同的整数——从第1座塔可访问的通信塔的索引。题目大意： 有n座通信塔，编号从1到n，以及m条双向电线连接它们。每座塔接受一定范围的频率，第i座塔接受的频率从l_i到r_i。如果存在一个频率x和一系列塔a=v_1, v_2, …, v_k=b，其中连续的塔之间通过电线直接连接，并且每座塔都接受频率x，则称塔b从塔a是可访问的。注意，可访问性不是传递的，即如果b从a可访问且c从b可访问，则c不一定从a可访问。任务是确定从第1座塔可访问的塔。 输入数据格式： 第一行包含两个整数n和m（1≤n≤2×10^5；0≤m≤4×10^5）——通信塔的数量和电线的数量。 然后是n行，第i行包含两个整数l_i和r_i（1≤l_i≤r_i≤2×10^5）——第i座塔可接受频率的边界。 然后是m行，第i行包含两个整数v_i和u_i（1≤v_i,u_i≤n；v_i≠u_i）——第i条电线连接的塔v_i和u_i。没有两条电线连接同一对塔。 输出数据格式： 在一行中，按升序打印从1到n的不同的整数——从第1座塔可访问的通信塔的索引。