UOJ Logo Universal Online Judge

UOJ

#854. 【JOISC2023】旅行

附件下载 统计

JOI 国是一个由 N 个岛屿构成的岛国,这 N 个岛屿编号为 1N。这些岛屿由 N1 座桥相连,这些桥编号为 1N1。桥 i (1iN1) 双向连接岛屿 AiBi。保证可以从一座岛屿出发,经过一定数量的桥到达任意其他岛屿。

在 JOI 国中,有 M 个旅游景点,从 1M 编号。景点 j (1jM) 位于岛屿 Cj 上。

Q 个旅行者,编号为 1Q。他们计划去 JOI 国旅游。每个旅行者按如下方式旅游:

  1. 旅行者选择一个岛屿 x (1xN),并乘飞机抵达岛屿 x
  2. 旅行者执行如下操作若干次,操作的顺序和种类任意
    • 旅行者选择目前岛上的一个景点并游览它
    • 旅行者通过一座桥移动到其他岛屿
  3. 旅行者乘飞机离开 JOI 国

旅行者 k (1kQ) 想要游览所有景点 Lk,Lk+1,,Rk。然而,由于预算有限,旅行者 k 希望最小化至少去过一遍的岛屿数。

给定 JOI 国和旅行者的信息,写一个程序计算对于每个 k (1kQ),旅行者 k 至少去过一遍的岛屿数的最小值。

输入格式

第一行三个整数 N,M,Q

接下来 N1 行,每行两个整数 Ai,Bi

接下来一行 M 个整数 C1,C2,,CM

接下来 Q 行,每行两个整数 Lk,Rk

输出格式

输出 Q 行,第 k 行输出一个整数,表示旅行者 k 至少去过一遍的岛屿数的最小值。

样例输入 1

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

样例输出 1

4
6

旅行者 1 按如下方式旅行,并游览景点 1,2,3

  1. 旅行者 1 到达岛屿 2
  2. 旅行者 1 游览岛屿 2 上的景点 1
  3. 旅行者 1 从岛屿 2 经过桥 1 到达岛屿 1
  4. 旅行者 1 从岛屿 1 经过桥 2 到达岛屿 3
  5. 旅行者 1 游览岛屿 3 上的景点 2
  6. 旅行者 1 从岛屿 3 经过桥 5 到达岛屿 6
  7. 旅行者 1 游览岛屿 6 上的景点 3
  8. 旅行者 1 从岛屿 6 离开 JOI 国

旅行者 1 至少到过一次的岛屿是岛屿 1,2,3,6。如果旅行者 1 至少到过一次的岛屿数小于等于 3,就不可能游览所有景点 1,2,3 了。因此第一行输出 4

旅行者 2 按如下方式旅行,并游览景点 4,5,6

  1. 旅行者 2 到达岛屿 3
  2. 旅行者 2 从岛屿 3 经过桥 6 到达岛屿 7
  3. 旅行者 2 游览岛屿 7 上的景点 6
  4. 旅行者 2 从岛屿 7 经过桥 6 到达岛屿 3
  5. 旅行者 2 从岛屿 3 经过桥 2 到达岛屿 1
  6. 旅行者 2 从岛屿 1 经过桥 1 到达岛屿 2
  7. 旅行者 2 从岛屿 2 经过桥 3 到达岛屿 4
  8. 旅行者 2 游览岛屿 4 上的景点 4
  9. 旅行者 2 从岛屿 4 经过桥 3 到达岛屿 2
  10. 旅行者 2 从岛屿 2 经过桥 4 到达岛屿 5
  11. 旅行者 2 游览岛屿 5 上的景点 5
  12. 旅行者 2 从岛屿 5 离开 JOI 国

旅行者 2 至少到过一次的岛屿是岛屿 1,2,3,4,5,7。如果旅行者 2 至少到过一次的岛屿数小于等于 5,就不可能游览所有景点 4,5,6 了。因此第二行输出 6

这组样例满足子任务 1,2,4,5,6 的限制。

样例输入 2

8 8 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 6 4 3 5 2 4 7
3 5
4 6
6 8
1 4
2 3
6 8
5 5
2 8
1 2

样例输出 2

3
4
6
6
3
6
1
6
3

这组样例满足子任务 1,2,3,6 的限制。

样例输入 3

10 7 9
6 5
3 6
9 3
8 3
7 8
7 1
2 5
7 10
8 4
9 4 10 1 10 7 6
4 4
1 3
1 3
6 7
3 6
3 3
1 5
2 5
1 2

样例输出 3

1
6
6
4
3
1
7
5
4

这组样例满足子任务 1,2,6 的限制。

数据范围

对于所有输入数据,满足:

  • 1N,M,Q105
  • 1Ai,BiN
  • 保证从一座岛屿出发,可以经过一定数量的桥到达任意其他岛屿
  • 1CjN
  • 1LkRkM

详细子任务附加限制及分值如下表所示。

子任务编号 附加限制 分值
1 N,M,Q300 5
2 N,M,Q2 000 5
3 Ai=i,Bi=i+1 7
4 L1=1,Rk+1=Lk+1,RQ=M 18
5 Ai=i+12,Bi=i+1,这里 x 表示不超过 x 的最大整数 24
6 无附加限制 41