Evolution Monsters

問題

ポケポケ地方には,(1,2,...,N)(1,2,...,N)NN種類のモンスターが生息しています.

モンスターにはレベルがあり,成長とともにレベルが上がっていきます.

また,モンスターの中には,進化することができるモンスターがおり,進化すると,モンスターの種類が変化します.モンスターAAがモンスターBBに変化する進化は,以下のように定められています.

  • 進化には進化石が必要で,進化ごとに定められたXX円の進化石を持たせた状態でモンスターAAがレベルアップしたとき,モンスターBBに進化することができます.進化後,使用した進化石はなくなります.
  • モンスターAAは,他のモンスターにも進化することができることがありますが,モンスターBBに直接進化することができるモンスターはモンスターAAだけです.
  • モンスターAAは,モンスターBB以外のモンスターにも,同じ値段の進化石で進化できることもありますし,値段が違うこともあります.(つまり,進化石の値段は,進化前のモンスターには依存しません.)
  • モンスターBBに進化したあと,どのように進化を遂げてもモンスターAAになることはありません.(つまり,すべての進化は不可逆的です.)

MM個の進化の条件が与えられます.i(1jM)i(1 \leq j \leq M)番目の進化条件は,XiX_i円の進化石を持たせた状態でモンスターAiA_iがレベルアップしたとき,モンスターBiB_iに進化することができることを示します.

あなたは,ポケポケ地方でQQ匹のモンスターを捕まえました.j(1jQ)j(1 \leq j \leq Q)番目に捕まえたモンスターPj,1P_{j,1}を,11回以上進化させることで,Pj,2P_{j,2}にしたいと考えています.jj回目に捕まえたモンスターそれぞれについて,モンスターPj,1P_{j,1}をモンスターPj,2P_{j,2}にすることができる場合は,モンスターPj,1P_{j,1}をどのモンスターに "まず" 進化させる必要があるか,および,モンスターPj,1P_{j,1}をモンスターPj,2P_{j,2}にするまでにかかるお金を求めなさい.モンスターPj,1P_{j,1}をどのように進化させていってもモンスターPj,2P_{j,2}にすることができない場合は IMPOSSIBLE と出力してください.

制約

  • 2N2×1052 \leq N \leq 2 \times 10^5
  • 0MN10 \leq M \leq N - 1
  • 1Qmin(2×105,N(N1))1 \leq Q \leq min(2 × 10^5, N(N-1))
  • 0Xi109(1iM)0 \leq X_i \leq 10^9 (1 \leq i \leq M)
  • 1Ai,Bi,Pj,1,Pj,2N(1iM,1jQ)1 \leq A_i, B_i, P_{j,1}, P_{j,2} \leq N (1 \leq i \leq M, 1 \leq j \leq Q)
  • BiBj(1i<jM)B_i \neq B_j (1 \leq i < j \leq M)
  • 任意のモンスターについて,11回以上の進化を遂げて自分自身にもう1度なることができるような進化の集合は与えられない
  • 入力は全て整数

入力

N M Q
X_1 A_1 B_1
X_2 A_2 B_2
...
X_M A_M B_M
P{1,1} P{1,2}
P{2,1} P{2,2}
...
P{Q,1} P{Q,2}

出力

i(1iQ)i(1 \leq i \leq Q)行目には,ii番目に捕まえたモンスターについて,答えが存在するとき,捕まえたときのレベル以降最初の進化における進化後のモンスターの種類と,モンスターPj,1P_{j,1}をモンスターPj,2P_{j,2}にするまでにかかるお金を空白区切りで出力し,存在しない時, IMPOSSIBLE と出力せよ.

monster_1 cost_1 もしくは IMPOSSIBLE
monster_2 cost_2 もしくは IMPOSSIBLE
...
monster_Q cost_3 もしくは IMPOSSIBLE

サンプル

入力例1

4 3 4
20 2 3
10 1 2
30 3 4
2 3
1 4
2 4
1 3

出力例1

3 20
2 60
3 50
2 30

入力例2

10 7 6
20 10 3
40 5 1
30 9 4
20 10 7
30 1 6
10 5 10
40 3 2
8 10
3 4
10 6
5 7
10 2
5 9

出力例2

IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
10 30
3 60
IMPOSSIBLE

提出


Go (1.21)