← 返回题目列表

Codeforces · 1814/F

F. 通讯塔

中文机器翻译题面 查看原题

有$$$n$$$个通信塔,编号从$$$1$$$到$$$n$$$,它们之间有$$$m$$$双向电线。每个塔都有其接受的特定频率集,其中第 $$$i$$$ 接受从 $$$l_i$$$ 到 $$$r_i$$$ 的频率。

假设塔 $$$b$$$ 可以从塔 $$$a$$$ 访问,如果存在频率 $$$x$$$ 和塔序列 $$$a=v_1, v_2, \dots, v_k=b$$$,其中序列中的连续塔通过电线直接连接,并且每个塔都接受频率 $$$x$$$。请注意,可访问性不是传递性的,即。 e 如果 $$$b$$$ 可以从 $$$a$$$ 访问,而 $$$c$$$ 可以从 $$$b$$$ 访问,则 $$$c$$$ 可能无法从 $$$a$$$ 访问。

你的任务是确定可从 $$$1$$$-st 塔进入的塔。

输入

第一行包含两个整数 $$$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$$$-st 塔访问的通信塔的索引。

示例

输入 #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

1 3 5 6

输入 #2

3 1
2 3
1 4
1 1
1 3

输出 #2

1

输入 #3

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

输出 #3

1 2 3 4 5