Communication Towers
Contest: Educational Codeforces Round 146 (Rated for Div. 2)
Difficulty rating: 2700
Tags: brute force, divide and conquer, dsu

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 format:
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 format:
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.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Example 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

Example output:
1 3 5 6

Example input:
3 1
2 3
1 4
1 1
1 3

Example output:
1

Editorial:
Let's consider the sweep line approach by the value of the variable $$$x$$$; the vertex $$$i$$$ is active from the moment $$$l_i$$$ to the moment $$$r_i$$$. And we have to find vertices that are reachable in the graph of active vertices from the vertex $$$1$$$. So, we rephrased the problem as follows: there are vertices that are active at some moments, and we want to get some information about connectivity during each moment of time. This is a standard offline dynamic connectivity problem which can be solved with a divide-and-conquer approach described here.
Now we are able to find the connectivity component of the $$$1$$$-th vertex for each value of $$$x$$$. It remains to understand how to combine answers for all values of $$$x$$$ fast enough. Let's try to visualize the components as vertices of a directed graph. We assign a vertex to each component, and when two components merge, we add two directed edges from the new vertex to the vertices corresponding to the components; and now we can use the reachability information in this graph. Each vertex of the original graph corresponds to one of the sinks in this graph; and sinks that correspond to the vertices of some component are reachable from the vertex corresponding to that component. To restore all the vertex indices later, we will mark all components containing the vertex $$$1$$$ while we run our dynamic connectivity approach. Then the vertex $$$v$$$ (of the original graph) is included in the answer if the vertex representing the component containing only the vertex $$$v$$$ is reachable from any of the marked vertices. Now, all you need to do is run DFS or BFS from all the marked vertices in the component graph.