← 返回题目列表

AtCoder · abc024_c

C. 民族大迁徙

中文机器翻译题面 查看原题

問題文

在高桥王国 有 N 个城市,每个城市都有 以 1 ~ N 整数编号。

在高桥王国 有 K 不同的民族居住在那里,i 第二个民族是城市。 我住在 S_i 。

高桥王国的族群有一种名为“民族大迁徙”的文化,他们每100年更换一次居住的城市。 基本上各民族同时进行“民族大迁徙”,但如果各民族在同一天迁徙,预计会出现拥堵,因此每天设置以下迁徙限制。 D 需要一天的时间。

  • i 当天城市号码为 L_i 以上 R_i 您可以按如下方式在城镇之间自由移动。禁止所有其他活动。

每个民族都遵守这些行动限制,并通过多个城市前往目的地城市。

i 第th族的目的地是城市。 T_i 。各族人民都希望尽快到达目的地。

查找每个种族的最早可能到达日期。

此外,任何种族群体 保证在 D 天内到达您的目的地。


入力

输入将以以下形式从标准输入给出。

N D K
L_1 R_1
L_2 R_2
:
L_D R_D
S_1 T_1
S_2 T_2
:
S_K T_K
  • 1 行中显示了高桥王国的城镇数量。 N(1 ≦ N ≦ 10^9) ,大迁徙花费的天数 D(1 ≦ D ≦ 10^4) ,居住在高桥王国的族群数量 来自行 K(1 ≦ K ≦ 100) 用空格分隔。
  • 2 从线 D 行数过多 i 在线 i 表示当天的行动限制。 2 整数 L_i, R_i(1 ≦ L_i ≦ R_i ≦ N) 用空格分隔。
  • D+2 从线 K 行数过多 i 在线 i 第th民族原来居住的城市 S_i( 1 ≦ S_i ≦ N),目的地城市 T_i (1 ≦ T_i ≦ N) 用空格分隔。此时 S_i ≠ T_i 成立。
  • 任何种族 保证您在 D 天内到达目的地。

出力

输出是 由 K 行组成。 打印第 i 在线 i 个族裔群体可以到达目的地的第一天。 还在输出末尾添加换行符。 第


入力例1

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

出力例1

2
4
8

1 个族群可以按如下方式移动: 您可以在 2 天后到达目的地。你不能移动得比这更快。

  • 1 当天所在城市 1 从城市出发 转至 4 。
  • 2 当天所在城市 4 从城市出发 转至 6 。

2 个族群可以按如下方式移动: 您可以在 4 天后到达目的地。你不能移动得比这更快。

  • 1 当天所在城市 2 从城市出发 转至 5 。
  • 4 当天所在城市 5 从城市出发 转至 7 。

3 个族群可以按如下方式移动: 您可以在 8 天后到达目的地。你不能移动得比这更快。

  • 3 当天所在城市 10 从城市出发 转至 9 。
  • 7 当天所在城市 9 从城市出发 转至 3 。
  • 8 当天所在城市 3 从城市出发 转至 1 。

入力例2

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

出力例2

10
4
2
2

入力例3

314159265 10 1
1 10000
500 12031
1414 113232
111111 777777
666661 23423423
12345678 123456789
111111111 314159265
112334 235235235
1 223445
314 1592
1 314159265

出力例3

7