二つの木

$N$ 頂点の木 $T_1$ が与えられます。頂点には $1,2,\cdots,N$ の番号が付いています。

同じ頂点を持つ二つの木 $T_1,T_2$ について、次の条件をともに満たす頂点集合 $S$ が存在しないとき、$T_1$ と は にあるといいます。

• $2\le |S|\le N-1$。
• $T_1$ において $S$ が誘導する部分グラフと、 において が誘導する部分グラフがともに連結である。

$T_1$ と良い関係にある木 $T_2$ が存在するか判定し、存在するならその一例を構成してください。

入力は標準入力から次の形式で与えられます。

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

各テストケースについて、次のように出力してください。

条件を満たす $T_2$ が存在しない場合、1 行に $-1$ を出力してください。

存在する場合、$N-1$ 行にわたって次の形式で出力してください。

• $1\le T\le 50\,000$。
• $3\le N\le 200\,000$。
• $1\le U_{}$ ()。