Evolution Monsters
問題
ポケポケ地方には,(1,2,...,N)のN種類のモンスターが生息しています.
モンスターにはレベルがあり,成長とともにレベルが上がっていきます.
また,モンスターの中には,進化することができるモンスターがおり,進化すると,モンスターの種類が変化します.モンスターAがモンスターBに変化する進化は,以下のように定められています.
- 進化には進化石が必要で,進化ごとに定められたX円の進化石を持たせた状態でモンスターAがレベルアップしたとき,モンスターBに進化することができます.進化後,使用した進化石はなくなります.
- モンスターAは,他のモンスターにも進化することができることがありますが,モンスターBに直接進化することができるモンスターはモンスターAだけです.
- モンスターAは,モンスターB以外のモンスターにも,同じ値段の進化石で進化できることもありますし,値段が違うこともあります.(つまり,進化石の値段は,進化前のモンスターには依存しません.)
- モンスターBに進化したあと,どのように進化を遂げてもモンスターAになることはありません.(つまり,すべての進化は不可逆的です.)
M個の進化の条件が与えられます.i(1≤j≤M)番目の進化条件は,Xi円の進化石を持たせた状態でモンスターAiがレベルアップしたとき,モンスターBiに進化することができることを示します.
あなたは,ポケポケ地方でQ匹のモンスターを捕まえました.j(1≤j≤Q)番目に捕まえたモンスターPj,1を,1回以上進化させることで,Pj,2にしたいと考えています.j回目に捕まえたモンスターそれぞれについて,モンスターPj,1をモンスターPj,2にすることができる場合は,モンスターPj,1をどのモンスターに "まず" 進化させる必要があるか,および,モンスターPj,1をモンスターPj,2にするまでにかかるお金を求めなさい.モンスターPj,1をどのように進化させていってもモンスターPj,2にすることができない場合は IMPOSSIBLE
と出力してください.
制約
- 2≤N≤2×105
- 0≤M≤N−1
- 1≤Q≤min(2×105,N(N−1))
- 0≤Xi≤109(1≤i≤M)
- 1≤Ai,Bi,Pj,1,Pj,2≤N(1≤i≤M,1≤j≤Q)
- Bi=Bj(1≤i<j≤M)
- 任意のモンスターについて,1回以上の進化を遂げて自分自身にもう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(1≤i≤Q)行目には,i番目に捕まえたモンスターについて,答えが存在するとき,捕まえたときのレベル以降最初の進化における進化後のモンスターの種類と,モンスターPj,1をモンスターPj,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
入力例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