$N$ 個の町と $N-1$ 個の道があります。
すべての町と道にはそれぞれ $1$ から $N$, $1$ から $N-1$ の番号がついています。
道 $i$ は町 $a_i$ と町 $b_i$ を距離 $d_i$ で双方向につないでいます。
最初はすべての道が通行可能な状態であり、どの町からもいくつかの道を通ることですべての町に行くことができます。
すいばかくんは最初、町 $1$ にいます。
$Q$ 個のクエリが与えられるので順番に処理してください。クエリは $3$ 種類あり、以下の形式で与えられます。
1 x
― すいばかくんが町 $x$ に移動する。ただし、このクエリ時点で、すいばかくんがいる町と町 $x$ は通行可能な $1$ つの道で直接つながれていることが保証される。2 y
― 道 $y$ が封鎖される。ただし、このクエリ時点で、道 $y$ は通行可能であることが保証される。3 z
― 道 $z$ が通行可能になる。ただし、このクエリ時点で、道 $z$ は封鎖されていることが保証される。さらに、各クエリを行った直後に、すいばかくんがその時点で通行可能な道のみを使って到達可能な町のうち、すいばかくんがいる町から一番遠い町の番号を昇順ですべて出力してください。
以下の形式で標準入力から与えられる。
$N$ $a_1$ $b_1$ $d_1$ $a_2$ $b_2$ $d_2$ $:$ $a_{N-1}$ $b_{N-1}$ $d_{N-1}$ $Q$ $Query_1$ $Query_2$ $:$ $Query_Q$
$Query_i$ は問題文にある $3$ 種類のクエリのいずれかの形式で与えらえる。
$Q$ 行出力せよ。 $i$ 行目には、$i$ 番目クエリ後の出力すべき町の番号が昇順で $v_1$, $v_2$, $...$, $v_c$ の $c$ 個であるとき、以下のように空白区切りで出力せよ。
$c$ $v_1$ $v_2$ $...$ $v_c$
6 2 4 1 1 2 1 4 6 1 2 3 1 4 5 1 5 2 5 2 3 1 2 3 5 1 4
1 6 2 3 4 3 1 3 4 1 5 2 1 3
$1$ つ目のクエリで、道 $5$ が封鎖されます。この直後に、すいばかくんが到達可能な町は $1$, $2$, $3$, $4$, $6$ であり、すいばかくんがいる町 $1$ からの距離はそれぞれ $0$, $1$, $2$, $2$, $3$ なので、答えは町 $6$ になります。
$2$ つ目のクエリで、道 $3$ が封鎖されます。この直後に、すいばかくんが到達可能な町は $1$, $2$, $3$, $4$ であり、すいばかくんがいる町 $1$ からの距離はそれぞれ $0$, $1$, $2$, $2$ なので、答えは町 $3$, $4$ になります。
$3$ つ目のクエリで、すいばかくんは町 $2$ に移動します。この直後に、すいばかくんが到達可能な町は $1$, $2$, $3$, $4$ であり、すいばかくんがいる町 $2$ からの距離はそれぞれ $1$, $0$, $1$, $1$ なので、答えは町 $1$, $3$, $4$ になります。
$4$ つ目のクエリで、道 $5$ が通行可能になります。この直後に、すいばかくんが到達可能な町は $1$, $2$, $3$, $4$, $5$ であり、すいばかくんがいる町 $2$ からの距離はそれぞれ $1$, $0$, $1$, $1$, $2$ なので、答えは町 $5$ になります。
$5$ つ目のクエリで、すいばかくんは町 $4$ に移動します。この直後に、すいばかくんが到達可能な町は $1$, $2$, $3$, $4$, $5$ であり、すいばかくんがいる町 $4$ からの距離はそれぞれ $2$, $1$, $2$, $0$, $1$ なので、答えは町 $1$, $3$ になります。
5 3 4 1 2 1 1 4 5 1 3 2 1 6 2 2 3 2 1 2 1 3 2 4 1 4
1 1 1 5 1 5 2 1 5 1 5 2 3 5