CF1814F Communication Towers

题目描述

给定一个 $n$ 个点 $m$ 条边的无向图，其中每个点 $i$ 会在 $[l_i,r_i]$ 这段时间出现。

输出哪些点能在某个时间 $x$ 和 $1$ 联通。

输入格式

第一行两个整数 $n \ m$ ( $1 \le n \le 2 \cdot 10^5$ ; $0 \le m \le 4 \cdot 10^5$ )。

下来 $n$ 行，每行两个整数 $l_i \ r_i$ ( $1 \le l_i \le r_i \le 2 \cdot 10^5$ ) 。

下来 $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$ 联通的点。

输入输出样例 #1

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

输入 #2

3 1
2 3
1 4
1 1
1 3

输出 #2

1

输入输出样例 #3

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