Migrated from Lutece 3111 Witch On The Holy Night

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：线段树分治、可撤销并查集

为了与天才人偶师苍崎橙子决战，苍崎青子与久远寺有珠决定早早在公园布下PLOY——“diddle diddle”，来为夜之童话的咏唱作准备。

有珠一共有 $n$ 只不同的diddle，编号为 $1\sim n$ ，其中第 $i$ 只diddle对魔术的回应存在激活频率区间 $[l_i,r_i]$ 。

具体地，对于某个特定的魔术频率 $x$ ，若 $x\in[l_i,r_i]$ 则我们称第 $i$ 只diddle处于激活状态。

同时她们预先在这些diddle间布下了用于传递魔术同调的线路，这样的线路一共有 $m$ 条。

每条线路形如 $u_i,v_i$ ，表示其连接了编号为 $u_i,v_i$ 的diddle，注意这样的连接是双向的。

定义魔术同调能从第 $a$ 只diddle传递到第 $b$ 只diddle，当且仅当存在某个魔术频率 $x$ 以及一个序列 $a=v_1,v_2,\cdots,v_k=b$ ，满足序列 $\{v_k\}$ 中的所有diddle都处于激活状态，且序列中相邻的两只diddle间都有线路将它们直接相连。

现在有珠想要知道，魔术同调能从 $1$ 号diddle传递到哪些diddle。

Input

输入的第一行包括两个正整数 $n,m$ ，分别表示有珠拥有的diddle数量以及布下的线路的数量。

在接下来的 $n$ 行中，每一行有两个正整数 $l_i,r_i$ ，表示第 $i$ 只diddle的激活频率区间。

在接下来的 $m$ 行中，每一行有两个正整数 $u_i,v_i$ ，表示第 $i$ 条线路连接了编号为 $u_i,v_i$ 的diddle。

保证任意两只diddle间不存在两条及以上的线路。

Output

输出共包括一行，包括魔术同调能从 $1$ 号diddle传递到的所有diddle的编号，按照升序输出。

Samples

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

Constraints

$1\le n\le 2\times 10^5,0\le m\le 4\times 10^5,1\le l_i\le r_i\le 2\times 10^5,1\le u_i,v_i\le n,u_i\ne v_i$

Note

注意魔术同调的传递关系可能不是transitive的，例如：

对于 $[l_1,r_1]=[1,2],[l_2,r_2]=[2,3],[l_3,r_3]=[3,4]$ ，且存在连接 $1\leftrightarrow 2,2\leftrightarrow 3$ 的情况

• 魔术同调能从 $1$ 号diddle能传递到 $2$ 号diddle（通过魔术频率 $2$ 和 $1\leftrightarrow 2$ 的线路）。
• 魔术同调能从 $2$ 号diddle能传递到 $3$ 号diddle（通过魔术频率 $3$ 和 $2\leftrightarrow 3$ 的线路）。
• 但魔术同调并不能从从 $1$ 号diddle能传递到 $3$ 号diddle（不存在某个魔术频率同时激活这三只diddle）。

Resources

2024 UESTC ICPC Training for Data Structures