UOJ Logo Universal Online Judge

UOJ

#848. 【JOISC2023】护照

附件下载 统计

护照是旅行者进入外国时在世界范围内使用的一种证件。

在一颗星球上有 N 个国家,从 1N 编号。每个国家签发一种护照。当旅行者持有国家 i (1iN) 签发的护照时,他可以进入国家 Li,Li+1,,Ri这里,保证旅行者可以进入所持护照的签发国。也就是说,保证 LiiRi

你有一个喜欢旅行的朋友。他梦想环游世界,但他最开始没有护照。因此,他计划通过重复如下两个操作来环游所有的 N 个国家。

  • 他获得了他目前所在国家签发的护照
  • 他移动到一个可以使用他目前拥有的护照入境的国家

当你听说了他的计划时,你想知道他是否可以实现他的计划,并且如果可以的话,他至少需要获得多少本护照。因为你不知道他住在哪儿,你假设他住在 Q 个可能的国家 X1,X2,,XQ

给定护照和他可能居住的国家,写一个程序计算对于所有可能,他是否能够环游所有 N 个国家,并且如果可能的话,计算他至少要获得多少本护照。

输入格式

第一行一个整数 N

接下来 N 行,每行两个整数 Li,Ri

接下来一行一个整数 Q

接下来 Q 行,每行一个整数 Xj

输出格式

输出 Q 行,对于第 j 行输出你的朋友住在国家 Xj 的情况的答案。如果他可以环游所有 N 个国家,输出他最少获得护照本数。否则输出 1

样例输入 1

4
1 3
2 4
2 3
4 4
1
1

样例输出 1

2

假设你的朋友住在国家 X1=1。如果他按照如下方法行动,他将环游所有 4 个国家。然后他将获得 2 本护照。

  1. 他获得国家 1 签发的护照。
  2. 使用国家 1 签发的护照,他移动到国家 2
  3. 他获得国家 2 签发的护照。
  4. 使用国家 1 签发的护照,他移动到国家 3
  5. 使用国家 2 签发的护照,他移动到国家 4

因为如果他获得小于等于 1 本护照的话无法实现计划,因此输出 2

这组样例满足所有子任务的限制。

样例输入 2

5
1 5
2 4
2 3
3 5
1 5
1
3

样例输出 2

4

假设你的朋友住在国家 X1=3。如果他按照如下方法行动,他将环游所有 5 个国家。然后他将获得 4 本护照。

  1. 他获得国家 3 签发的护照。
  2. 使用国家 3 签发的护照,他移动到国家 2
  3. 他获得国家 2 签发的护照。
  4. 使用国家 2 签发的护照,他移动到国家 4
  5. 他获得国家 4 签发的护照。
  6. 使用国家 4 签发的护照,他移动到国家 5
  7. 他获得国家 5 签发的护照。
  8. 使用国家 5 签发的护照,他移动到国家 1

因为如果他获得小于等于 3 本护照的话无法实现计划,因此输出 4

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

样例输入 3

5
1 1
2 3
1 5
3 4
5 5
5
1
2
3
4
5

样例输出 3

-1
2
1
2
-1

例如,如果你的朋友住在国家 X3=3,如果他获得了国家 3 签发的护照,他可以按 1,2,4,5 的顺序前往这些国家来实现计划。因此,第三行输出 1

另一方面,如果你的朋友住在国家 X5=5,即使他获得了国家 5 签发的护照,他也不可能进入其他国家。因此,他不能实现计划。因此第五行输出 1

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

样例输入 4

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

样例输出 4

-1
-1
-1
-1

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

数据范围

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

  • 2N2×105
  • 1LiiRiN
  • 1QN
  • 1XjN,Xj<Xj+1

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

子任务编号 附加限制 分值
1 Q=1,X1=1 6
2 N300,Q=1 16
3 N2 500,Q=1 24
4 N2 500 8
5 无附加限制 46

时间限制:2s

空间限制:1024MB