火车旅行
题号：NC53212
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

题目译自 JOISC 2017 Day2 T3「鉄道旅行 / Railway Trip」
某条铁路线（非环线）有N站，依次编号为。这条线路上跑着K类列车，编号为。每种列车都是双向运行的。
这条铁路线上的每个车站都有个旅客流量，旅客流量是一个的正整数。车站的旅客流量为L_i，。
第j类列车在且只在旅客流量的车站停车。现有Q名旅客，依次编号为，旅客的起点是车站A_k，终点是B_k。假设这些旅客只能靠这条铁路线移动。
对于每个旅客，求这名旅客的途中至少要停几次站（不含该旅客的起终点站）。保证同一名旅客的起点与终点不同。允许走回头路。

输入描述:

第一行有三个整数N,K,Q，用空格分隔。
在接下来的N行中，第i行有一个整数L_i。
在接下来的Q行中，第k行有两个整数A_k,B_k。

输出描述:

输出共Q行，每行一个整数，表示旅客k最少的停站次数。
示例1

输入

复制 
9 3 3
3
1
1
1
2
2
2
3
3
2 4
4 9
6 7

输出

复制 
1
3
0

说明

旅客1从车站2出发，可以直接坐1类车抵达车站4。中途站只有车站3。
旅客2从车站4出发，可以先坐1类车到车站5，再换乘2类车坐到车站1，再换乘3类车坐到车站9。中途站为车站5,1,8。
旅客3从车站6出发，直接坐1类车抵达车站7。
示例2

输入

复制 
5 2 1
2
1
1
1
2
1 4

输出

复制 
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

输出

复制 
2
1
1
3
2
0
3
4
0
1
3
4
1
2
2

备注:

对于所有数据，。

CC-BY-SA，感谢LOJ分享，译文来自https://loj.ac/problem/2395