Kalaba
問題文
最小全域木を求めるアルゴリズムに，Kalaba のアルゴリズムがあります．アルゴリズムは以下の通りです．
- 適当な全域木を求める．
- グラフの残りの各辺 \(e\) について，以下のような操作をおこなう．
- いまある全域木に辺 \(e\) を追加する．
- 追加してできた閉路における辺のうち，重みが最大のものを削除して，新たな全域木を得る．
指定された全域木と，グラフの残りの辺の順序に対し，Kalaba のアルゴリズムで最小全域木を求める過程において各ステップで削除される辺の重みをすべて求めてください．この問題の制約において，すべてのステップで削除される辺が一意に定まることが保証されます．
制約
- \(1 \le N \le 200000 = 2 \times 10^5\)
- \(1 \le M \le 200000 = 2 \times 10^5\)
- \(1 \le A_i,\, B_i,\, A^\prime_i,\, B^\prime_i \le N\)
- \((A_1,\, B_1),\, (A_2,\, B_2),\, \dots,\, (A_{N-1},\, B_{N-1})\) は木をなす
- \(1 \le C_i,\, C^\prime_i \le 1000000000 = 10^9\)
- \(C_1,\, C_2,\, \dots,\, C_{N-1},\, C^\prime_1,\, C^\prime_2,\, \dots,\, C^\prime_M\) は相異なる
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます．
| 入力 |
\(N\, M\)
\(A_1\, B_1\, C_1\)
\(A_2\, B_2\, C_2\)
\(\vdots\)
\(A_{N-1}\, B_{N-1}\, C_{N-1}\)
\(A^\prime_1\, B^\prime_1\, C^\prime_1\)
\(A^\prime_2\, B^\prime_2\, C^\prime_2\)
\(\vdots\)
\(A^\prime_{M}\, B^\prime_{M}\, C^\prime_{M}\) |
- \(1\) 行目に，グラフの頂点数 \(N\), グラフの残りの辺数 \(M\) が与えられます．
- 続く \(N - 1\) 行に，\(1 + i\) 行目には \(A_i,\, B_i,\, C_i\) が半角スペース区切りで与えられます．これは，全域木の \(i\) 番目の辺が頂点 \(A_i\) と \(B_i\) を 重み \(C_i\) でつないでいることを表します．
- 続く \(M\) 行に，\(N + i\) 行目には \(A^\prime_i,\, B^\prime_i,\, C^\prime_i\) が半角スペース区切りで与えられます．これは，Kalaba のアルゴリズムで \(i\) 番目に追加される辺が頂点 \(A^\prime_i\) と \(B^\prime_i\) を 重み \(C^\prime_i\) でつないでいることを表します．
出力
合計 \(M\) 行出力してください．
\(i\) 行目には，Kalaba のアルゴリズムで \(i\) 番目に削除される辺の重みを整数で出力してください．
最後に改行してください．