頂点に \(1\) から \(N\) の番号が付いた \(N\) 頂点からなる単純連結無向グラフ \(G\) があります。\(G\) には重みを持つ辺が \(M\) 本あり、\(i\) 番目の辺は頂点 \(A_i\) と \(B_i\) を結ぶ重みが \(C_i\) の辺です。
単純連結無向グラフ \(G'\) に対して、\(f(G', i, j)\) を以下で定義します。
\(Q\) 個のクエリが与えられます。
\(j\) 番目のクエリでは、\(G\) に 頂点 \(X_j\) と \(Y_j\) を結ぶ重み \(Z_j\) の辺を追加したグラフを \(G_j\) としたときの \(\min(f(G_j, V_j, 1), f(G_j, V_j, 2), ..., f(G_j, V_j, N))\) を求めてください。ただし、\(G_j\) は単純であることが保証されます。
\(1\) つの入力につき \(T\) 個のテストケースが与えられます。
入力は以下の形式で標準入力から与えられます。
| \(T\) | |
| \(\mathrm{case}_{1}\) | |
| \(\mathrm{case}_{2}\) | |
| \(\vdots\) | |
| \(\mathrm{case}_{T}\) |
\(t\) 番目のテストケース \(\mathrm{case}_t\) は以下の形式で与えられます。
| \(N~M\) | |
| \(A_1~B_1~C_1\) | |
| \(A_2~B_2~C_2\) | |
| \(\vdots\) | |
| \(A_M~B_M~C_M\) | |
| \(Q\) | |
| \(X_1~Y_1~Z_1~V_1\) | |
| \(X_2~Y_2~Z_2~V_2\) | |
| \(\vdots\) | |
| \(X_Q~Y_Q~Z_Q~V_Q\) |
入力は以下の制約をすべて満たします。
以下の形式で出力してください。
| \(T\) | |
| \(\mathrm{answer}_{1}\) | |
| \(\mathrm{answer}_{2}\) | |
| \(\vdots\) | |
| \(\mathrm{answer}_{T}\) |
\(t\) 番目のテストケースへの出力 \(\mathrm{answer}_t\) は \(Q\) 行から構成し、その中の \(q\) 行目には \(q\) 番目のクエリに対する答えを出力してください。
以下の追加制約を満たすデータセットに正解した場合、部分点が与えられます。
23 21 2 12 3 111 3 2 13 21 2 22 3 211 3 1 1
3 4
14 31 2 31 3 41 4 512 3 6 4
10
16 61 2 21 3 42 4 33 4 24 5 94 6 225 6 2 13 6 4 2
11 11
上の図は、 \(1\) つ目の入力例の \(1\) つ目のテストケースにおける \(G_1\) です。赤い辺が追加された辺です。
walkとして、頂点を \(1, 3, 1\) の順に辿ることで、 \(\min(w_1,w_2,...,w_k)+\max(w_1,w_2,...,w_k)\) は \(4\) になります。また、この値を \(5\) 以上にすることはできないため、 \(f(G_1, 1, 1) = 4\) となります。
頂点を \(1, 3, 2\) の順に辿ることで、 \(\min(w_1,w_2,...,w_k)+\max(w_1,w_2,...,w_k)\) は \(3\) になります。また、この値を \(4\) 以上にすることはできないため、 \(f(G_1, 1, 2) = 3\) となります。
頂点を \(1, 3\) の順に辿ることで、\(\min(w_1,w_2,...,w_k)+\max(w_1,w_2,...,w_k)\) は \(4\) になります。また、この値を \(5\) 以上にすることはできないため、 \(f(G_1, 1, 3) = 4\) となります。
したがって、\(\min(f(G_1, 1, 1), f(G_1, 1, 2), f(G_1, 1, 3)) = 3\) です。
\(1\) つ目の入力例は \(1\) つ目の部分点制約を満たします。
\(2\) つ目の入力例は \(2\) つ目の部分点制約を満たします。