Alice 與 Bob 擁有一棵包含 $2N$ 個節點的樹 $T$，節點編號為 $1$ 到 $2N$。

Bob 有一個整數 $K$，並希望能找到 $N$ 個數對 $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$，使得 $1$ 到 $2N$ 中的每個整數恰好在其中一個數對中出現一次，且距離總和 $\sum_{i=1}^N \text{dist}(X_i, Y_i) = K$，其中 $\text{dist}(X_i, Y_i)$ 表示樹中節點 $X_i$ 與 $Y_i$ 之間的距離，亦即 $X_i$ 與 $Y_i$ 之間（唯一）路徑上的邊數。

Alice 不希望 Bob 成功。她可以執行以下操作：

• 從 $T$ 中移除一條邊 $(U, V)$。
• 加入一條新邊 $(A, B)$，使得 $T$ 仍然是一棵樹。

請注意，允許選擇同一條邊進行刪除與加入，這只會讓樹保持原狀。

請幫助 Alice 找到一條應該刪除的邊 $(U, V)$ 與一條應該加入的邊 $(A, B)$。若有多組解，你可以找出其中任意一組。

可以證明，在本題的限制條件下，總是能夠刪除一條邊並加入一條邊，使得不存在 $N$ 個數對 $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ 滿足 $1$ 到 $2N$ 的每個整數恰好在其中一個數對中出現一次且距離總和等於 $K$。

輸入格式

輸入以下列格式給出：

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

輸出格式

對於每組測試資料，輸出兩行：

第一行應包含兩個整數 $U$ 與 $V$ — 表示要刪除邊 $(U, V)$。

第二行應包含兩個整數 $A$ 與 $B$ — 表示要加入邊 $(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：初始的樹中 Bob 有辦法獲得 $K = 4$ 的分數，例如選擇數對 $(1, 4)$ 與 $(2, 3)$。Alice 刪除邊 $(1, 2)$ 並加入 $(1, 3)$。在這棵新樹中，Bob 無法獲得 $4$ 的分數。