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