G: 一番遠い町

問題文

$N$ 個の町と $N-1$ 個の道があります。

すべての町と道にはそれぞれ $1$ から $N$, $1$ から $N-1$ の番号がついています。

道 $i$ は町 $a_i$ と町 $b_i$ を距離 $d_i$ で双方向につないでいます。

最初はすべての道が通行可能な状態であり、どの町からもいくつかの道を通ることですべての町に行くことができます。

すいばかくんは最初、町 $1$ にいます。

$Q$ 個のクエリが与えられるので順番に処理してください。クエリは $3$ 種類あり、以下の形式で与えられます。

  • クエリ $1$ : 1 x ― すいばかくんが町 $x$ に移動する。ただし、このクエリ時点で、すいばかくんがいる町と町 $x$ は通行可能な $1$ つの道で直接つながれていることが保証される。
  • クエリ $2$ : 2 y ― 道 $y$ が封鎖される。ただし、このクエリ時点で、道 $y$ は通行可能であることが保証される。
  • クエリ $3$ : 3 z ― 道 $z$ が通行可能になる。ただし、このクエリ時点で、道 $z$ は封鎖されていることが保証される。

さらに、各クエリを行った直後に、すいばかくんがその時点で通行可能な道のみを使って到達可能な町のうち、すいばかくんがいる町から一番遠い町の番号を昇順ですべて出力してください。

制約

  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq a_i, b_i \leq N$, $a_i \neq b_i$
  • $1 \leq d_i \leq 10^6$
  • $1 \leq Q \leq 2 \times 10^5$
  • クエリ $1$ において、$1 \leq x \leq N$ を満たす。また、このクエリ時点で、すいばかくんがいる町と町 $x$ は通行可能な $1$ つの道で直接つながれている。
  • クエリ $2$ において、$1 \leq y \leq N-1$ を満たす。また、このクエリ時点で、道 $y$ は通行可能である。
  • クエリ $3$ において、$1 \leq z \leq N-1$ を満たす。また、このクエリ時点で、道 $z$ は封鎖されている。
  • $i$ 番目のクエリで出力すべき町の個数を $c_i$ とするとき、$\sum_{i=1}^{Q}c_i \leq 4 \times 10^5$ を満たす。
  • 入力はすべて整数である。

入力

以下の形式で標準入力から与えられる。

$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$

入力例 1

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

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$ になります。

入力例 2

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

出力例 2

1 1
1 5
1 5
2 1 5
1 5
2 3 5