Alice と Bob は、$1$ から $2N$ までの番号が付けられた $2N$ 個の頂点からなる木 $T$ を持っています。

Bob は整数 $K$ を持っており、$1$ から $2N$ までの各整数がちょうど 1 つの組に現れ、かつ距離の総和が $\sum_{i=1}^N \text{dist}(X_i, Y_i) = K$ となるような $N$ 個の組 $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ を見つけたいと考えています。ここで $\text{dist}(X_i, Y_i)$ は木における頂点 $X_i$ と $Y_i$ の間の距離、すなわち $X_i$ と $Y_i$ を結ぶ（唯一の）パス上の辺の本数を表します。

Alice は Bob を成功させたくありません。彼女は以下の操作を行うことができます。

• $T$ から辺 $(U, V)$ を 1 本取り除く。
• $T$ が木のままであるように、新しい辺 $(A, B)$ を 1 本追加する。

削除する辺と追加する辺として同じ辺を選ぶことも許されており、その場合は元の木のままになることに注意してください。

Alice のために、削除すべき辺 $(U, V)$ と追加すべき辺 $(A, B)$ を 1 組見つけてください。解が複数存在する場合は、どれを求めても構いません。

この問題の制約の下では、ある辺を削除してある辺を追加することで、$1$ から $2N$ までの各整数がちょうど 1 つの組に現れ、かつ距離の総和が $K$ に等しくなるような $N$ 個の組 $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ が存在しないようにすることが常に可能であることが証明できます。

入力

入力は以下の形式で与えられます。

$$T$$ $$N\ K$$ $$U_1\ V_1$$ $$U_2\ V_2$$ $$\vdots$$ $$U_{{2N-1}}\ V_{{2N-1}}$$ $$\vdots$$

• 入力される値はすべて整数である。
• $1 \le T \le 10^4$
• $2 \le N \le 2 \times 10^5$
• $1 \le K \le 10^{12}$
• $1 \le U_i, V_i \le 2N$
• 与えられる辺は木をなすことが保証される。
• すべてのテストケースにおける $N$ の総和は $2 \times 10^5$ を超えないことが保証される。

出力

各テストケースについて、2 行出力してください。

1 行目には、削除する辺 $(U, V)$ を表す 2 つの整数 $U$ と $V$ を出力してください。

2 行目には、追加する辺 $(A, B)$ を表す 2 つの整数 $A$ と $B$ を出力してください。

解が複数存在する場合は、どれを出力しても構いません。

入出力例

入力 1

2
2 20
1 2
2 3
3 4
2 4
1 2
2 3
3 4

出力 1

1 2
1 2
1 2
1 3

注記

テストケース 1：最初の木の時点で Bob がスコア $K = 20$ を得る方法は存在しないため、Alice は単に既存の任意の辺を削除してそのまま追加すればよいです。

テストケース 2：最初の木では、例えば組 $(1, 4)$ と $(2, 3)$ を選ぶことで Bob はスコア $K = 4$ を得ることができます。Alice は辺 $(1, 2)$ を削除し、$(1, 3)$ を追加します。この新しい木では、Bob はスコア $4$ を得ることができません。