#214503. [JOISC 2017] 火车旅行 / Railway Trip

JOI 铁路公司运营一条铁路。在 JOI 铁路的线路上，有 个车站沿直线排列，编号从 到 。对于每个 （），车站 与车站 由一条铁轨连接。

JOI 铁路公司运营 种类型的列车，每种列车均双向运行。列车类型用 到 （含）之间的整数表示。每个车站有一个“等级”，也是一个 到 （含）之间的整数。对于每个 （），车站 的等级为 。两端的车站，即车站 和车站 ，等级均为 。

类型为 （）的列车会在所有等级大于等于 的车站停靠，且不在其他任何车站停靠。由于两端的车站（即车站 和车站 ）等级均为 ，因此所有列车均在这两个车站停靠。

每天都有许多乘客使用 JOI 铁路。在旅途中，他们可以乘坐方向与目的地相反的列车，或者直接经过目的地。但在旅行结束时，他们必须在目的地车站下车。他们不喜欢在车站过多停靠，因此会尽量选择中间停靠站数量最少的路线，而不论经过的车站总数或换乘次数。若乘客在某个车站下车换乘，我们将其计为一次停靠。起点站的首次停靠和终点站的最后一次停靠不计入中间停靠站。

你的任务是编写一个程序，能够回答每位乘客的最小中间停靠站数量的查询。

任务

给定 JOI 铁路的信息，以及每位乘客的起始站和目的地，编写一个程序，能够回答每位乘客的最小中间停靠站数量的查询。

从标准输入读取以下数据：

• 输入的第一行包含三个以空格分隔的整数 、、。这表示 JOI 铁路有 个车站，有 种类型的列车，并给出 个关于两站之间旅行的查询。
• 接下来的 行中，第 行（）包含一个整数 ，表示车站 的等级。
• 接下来的 行中，第 行（）包含两个以空格分隔的整数 、。这表示第 位乘客的起始站和目的地分别为车站 和 。

向标准输出写入 行。第 行（）包含从车站 到车站 的路线中最小的中间停靠站数量。

样例输入 1

9 3 3
3
1
1
1
2
2
2
3
3
2 4
4 9
6 7

样例输出 1

1
3
0

样例输入 2

5 2 1
2
1
1
1
2
1 4

样例输出 2

1

样例输入 3

15 5 15
5
4
1
2
3
1
1
2
4
5
4
1
5
3
5
8 1
11 1
5 3
6 11
9 12
15 14
15 2
3 12
2 1
4 8
15 5
12 6
1 13
13 8
14 9

样例输出 3

2
1
1
3
2
0
3
4
0
1
3
4
1
2
2

样例 1 解释

在本样例输入中，给出了三个关于两站之间旅行的查询：

• 第一个查询是关于从车站 2 到车站 4 的旅行。若乘客乘坐类型为 1 的列车从车站 2 直达车站 4，则仅有一个中间停靠站，即车站 3。
• 第二个查询是关于从车站 4 到车站 9 的旅行。若乘客先乘坐类型为 1 的列车从车站 4 到车站 5，再乘坐类型为 2 的列车从车站 5 到车站 1，最后乘坐类型为 3 的列车从车站 1 到车站 9，则共有三个中间停靠站，分别为车站 5、1 和 8。
• 第三个查询是关于从车站 6 到车站 7 的旅行。若乘客乘坐类型为 2 的列车从车站 6 直达车站 7，则无中间停靠站。

样例 2 解释

请注意，乘客在旅途中可以经过目的地车站。

数据范围

所有输入数据均满足以下条件：

• 。
• 。
• 。
• （）。
• （）。
• （）。
• （）。

子任务

共有 4 个子任务。每个子任务的得分及额外约束如下：

子任务 1 [5 分]

• 。
• 。
• 。

子任务 2 [15 分]

• 。

子任务 3 [25 分]

• 。

子任务 4 [55 分]

无额外约束。

翻译由 Qwen3-235B 完成