この問題について

この問題は、高専プロコンというイベントで配布する宣伝用紙のために、高専競プロ鯖 が作成したものです。高専生の方も、そうでない方も、ぜひ気軽に解いてみてください！

また、大まかな解説については yukicoder 内の解説に記載していますが、余裕があれば競技プログラミング未経験者向けの解説記事を作るかもしれません。

問題難易度について

この問題には、初心者から上級者まで楽しめるよう、部分点が設定されています。

各 Subtask の推定難易度を AtCoder の Difficulty に換算すると、以下のようになります。

• Subtask1：灰
• Subtask2：茶
• Subtask3：緑
• Subtask4：水
• Subtask5：青
• Subtask6(満点)：黄

また、すべての Subtask で C++23 と Python(PyPy3) の 想定解での正解 を確認しています。ただし、Python(PyPy3) については時間制限が厳しい Subtask も存在するため、同じ計算量でも実装によっては TLE となる可能性があります。その場合は生成AIなどを用いて、プログラムを C++ に変換することを推奨します。

問題文

高専太郎くんが住む K 県には $N$ 軒のうどん屋と $M$ 本の道路があります。うどん屋 $i\ (1 \le i \le N)$ は系列 $A_i$ に属しており、道路 $j$ $(1 \le j \le M)$ は店 $u_j$ と店 $v_j$ を双方向に繋いでいます。

また、K 県では各道路に 巡礼度 と呼ばれる整数値が設定されています。道路 $j$ には巡礼度 $w_j$ が設定されており、この道路は巡礼度を $w_j$ 以上持っている人のみ通行できます。

$Q$ 個のクエリが与えられるので、それぞれについて次の問題を解いてください。 $k\ (1 \le k \le Q)$ 番目のクエリは次のとおりです。

整数 $s_k,c_k$ が与えられます。

太郎くんは店 $s_k$ を始点として、到達可能な全てのうどん屋を訪れ、それぞれの店が属する系列のうどんを回収します。

太郎くんが $c_k$ 種類以上の系列のうどんを回収するために必要な巡礼度の最小値を求めてください。ただし、太郎くんがどれだけ巡礼値を持っても $c_k$ 種類以上の系列のうどんを回収することが不可能な場合は -1 を出力してください。

入力

$N\ M\ Q$
$A_1\ A_2\ \cdots\ A_N$
$u_1\ v_1\ w_1$
$u_2\ v_2\ w_2$
$\vdots$
$u_M\ v_M\ w_M$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

$k$ 番目のクエリ $\text{query}_k$ は以下の形式で与えられます。

$s_k\ c_k$

制約

• 入力はすべて整数
• $1 \le N \le 2\times 10^5$
• $0 \le M \le 2\times 10^5$
• $1 \le Q \le 2\times 10^5$
• $1 \le A_i \le N$
• $1 \le u_j,\ v_j \le N$
• $1 \le w_j \le 10^9$
• $1 \le s_k,\ c_k \le N$
• どの $2$ つの店の間も、いくつかの道路を通ることで互いに行き来できる
• 同じ $2$ つの店を直接結ぶ道路は $2$ 本以上存在しない

出力

各クエリの答えを改行区切りで出力してください。

また、最後の出力の末尾にも改行を入れてください。

各 Subtask の制約は、それ以前の Subtask の制約を引き継ぐとは限りません。 例えば、Subtask $3$ の制約を満たすテストケースが、Subtask $2$ の制約を満たすとは限りません。

テストケースは Subtask の小さい番号から順に実行されます。yukicoder の制約上、TLE をするとその時点でジャッジが打ち切られるため、必要に応じて assert 関数などを用いて、対象外の Subtask ではプログラムを終了することを推奨します。

なお、すべての Subtask に正解することで AC となります。

サンプル

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

2
3

8 10 6
1 2 3 4 5 6 7 8
1 2 132333
1 7 13100
4 3 108976
5 6 3911
1 4 55714
4 5 1629
2 8 59400
8 7 135765
2 3 79481
6 7 115502
1 2
7 2
5 2
5 3
5 6
5 8

13100
13100
1629
3911
108976
108976

1 0 1
1
1 1

0

16 19 5
6 11 9 12 12 8 3 12 3 14 2 12 16 8 9 4
3 15 496513734
3 10 221107446
3 16 526825332
3 11 800915964
10 14 569184838
4 15 653916233
13 16 234134147
12 14 205768486
2 10 921532315
8 15 825947957
4 9 632723847
1 15 365777683
6 9 572312537
3 5 731148890
7 10 37197809
1 11 251721087
10 12 77987919
9 10 142437714
6 14 57202237
1 13
6 10
9 3
9 11
3 16

-1
921532315
142437714
-1
-1

15 14 15
10 4 14 13 7 7 4 6 13 2 5 4 15 14 11
4 14 18416279
4 6 508296217
4 15 170711604
1 15 382401200
6 8 819754912
6 11 481535667
2 14 612834952
8 13 588801115
2 5 427235646
1 9 262676442
7 8 694213369
5 12 513030814
3 6 772381404
10 12 449299186
6 15
10 1
10 3
4 8
1 12
13 8
10 5
5 13
4 3
6 5
2 1
5 8
4 11
8 13
10 7

-1
0
513030814
612834952
-1
819754912
612834952
-1
170711604
508296217
0
612834952
-1
-1
612834952