C - 民族大移動 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋王国には N 個の街があり、それぞれ 1 ～ N の整数によって番号付けされています。

高橋王国には K 種類の民族が住んでおり、i 番目の民族は街 S_i に住んでいます。

高橋王国の民族たちには、百年に一回住む街を変える「民族大移動」という文化が有ります。 基本的には全民族が同時期に「民族大移動」を行うのですが、全く同じ日に全民族が移動すると混雑が予想されるため、 以下の様な移動制限を毎日設けて、 D 日かけて行います。

  • i 日目は 街の番号が L_i 以上 R_i 以下であるよう街の間を自由に行き来できる。それ以外の行き来は禁止される。

各民族はこの移動制限を守り、いくつかの街を経由しながら目的地の街まで移動します。

i 番目の民族の目的地は街 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 番目の民族の初め住んでいる街 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