P9166 [NOI Qualifier Joint Contest 2023] Train Station

There are $n$ train stations in a straight line, numbered from $1$ to $n$. There are $m$ railway tracks in total, and each track covers an interval of stations $[l_i, r_i]$. At a station covered by multiple tracks, when a train passes through, it may switch tracks there. However, the train cannot turn around, and can only run in one direction (that is, it can only keep moving toward station $1$ or keep moving toward station $n$). Person A starts from station $x$, meaning they board any train that passes through $x$ (this train may also depart from station $x$). This train may run on any track that covers station $x$, and its direction may be toward $1$ or toward $n$. After boarding, Person A falls asleep, and only wakes up when the train stops at the terminal station of some track. Ask which stations Person A may finally reach. Note: The train must travel through at least one station. Also, after switching tracks, the train will not stop immediately; instead, it will continue moving along the current track.

The first line contains three positive integers $n, m, x$, representing the number of stations, the number of tracks, and Person A’s starting station. The next $m$ lines each contain two positive integers $l_i, r_i$, representing the operating interval of a track.

Output one line containing several positive integers separated by single spaces, representing the stations that Person A may finally reach. Output them in increasing order of station number.

**Sample 1 Explanation** Starting from station $4$, if the train takes the first track, it can reach the terminal station $3$, or it can then continue along the third track to reach the terminal station $1$. Starting from station $4$, if the train takes the second track, it can reach the terminal station $6$, or it can switch to the fourth track at station $5$ and reach the terminal station $7$. So the final output in order is $1, 3, 6, 7$. **Constraints** For all testdata, it is guaranteed that $1 \le n, m \le 2 \times 10^5$, $1 \le x \le n$, $1 \le l_i < r_i \le n$. |Test Point|$n, m \le$|Special Property| |:-:|:-:|:-:| |1|$50$|None| |2|$50$|None| |3|$5000$|None| |4|$5000$|None| |5|$5000$|None| |6|$2 \times 10^5$|A| |7|$2 \times 10^5$|A| |8|$2 \times 10^5$|None| |9|$2 \times 10^5$|None| |10|$2 \times 10^5$|None| Special Property A: It is guaranteed that $x = 1$. Translated by ChatGPT 5