#P9166. [省选联考 2023] 火车站

[省选联考 2023] 火车站

题目描述

nn 个火车站排成一条直线,从 11nn 编号。一共有 mm 条火车轨道,每条轨道覆盖一段火车站区间 [li,ri][l_i, r_i]

对于一个被多条火车轨道覆盖的火车站,火车在经过这里的时候,可以在此处改变轨道。但是火车无法掉头,只能朝着一个方向运行(即只能一直往 11 的方向开或者一直往 nn 的方向开)。

小 A 从火车站 xx 出发,即搭上了经过 xx 的任意一列火车(这列火车也可能是从车站 xx 出发)。这列火车可能行驶在火车站 xx 所处的任一条轨道上,其运行方向既可能是往 11 的方向开,也可能是往 nn 的方向开。小 A 上车后就开始昏睡,直到乘坐的火车到达某条线路的终点站停下,他才醒过来。问小 A 最后可能到达的车站。

注意:火车应运行至少一个车站,且火车切换轨道后不会立刻停下来,而是会继续沿着当前轨道前进。

输入格式

输入的第一行包含三个正整数 n,m,xn, m, x,分别表示火车站的数量,火车轨道的数量以及小 A 初始的起点。

接下来 mm 行,每行包含两个正整数 li,ril_i, r_i,表示一条火车轨道运行的区间。

输出格式

输出一行,包含若干个用单个空格分隔的正整数,表示小 A 最后可能到达的车站,按照车站编号升序排序输出。

7 5 4
3 4
4 6
1 3
5 7
4 6

1 3 6 7

提示

【样例 1 解释】

火车从车站 44 出发,沿着第一条轨道可以运行到终点 33,也可以接着沿第三条轨道运行到终点 11

火车从车站 44 出发,沿着第二条轨道可以运行到终点 66,也可以在车站 55 换到第四条轨道运行到终点 77

所以最终按顺序输出 1,3,6,71, 3, 6, 7

【数据范围】

对于所有的数据,保证 1n,m2×1051 \le n, m \le 2 \times 10^51xn1 \le x \le n1li<rin1 \le l_i < r_i \le n

测试点 n,mn, m \le 特殊性质
1 5050
2
3 50005000
4
5
6 2×1052 \times 10^5 A
7
8
9
10

特殊性质 A:保证 x=1x = 1