Piggy（他在閒暇時管理星際連接協定委員會）正面臨一個棘手的硬體難題。最新的通訊網格由 $n$ 個中繼站組成，並透過 $(n - 1)$ 條光纖鏈路連接成樹狀結構，現在終於準備好部署了。然而，系統啟動時必須極度謹慎。

啟動過程涉及沿著特定路徑發射雷射脈衝。路徑定義為兩個站點之間唯一的簡單路徑。由於存在「量子回流干擾」（一種讓委員會律師徹夜難眠的現象）的災難性風險，必須嚴格遵守以下協定：

• 傳輸路徑必須一條一條地建立。
• 為了防止電力湧浪，每條新建立的路徑與先前任何路徑所啟動的站點集合之間，最多只能共享一個站點。

形式上，令 $S$ 為當前已啟動站點的集合。對於任何由站點集合 $V(P)$ 組成的新路徑 $P$，必須滿足條件 $|V(P) \cap S| \le 1$。一旦路徑成功發射，該路徑上的所有站點都被視為已啟動集合 $S$ 的一部分。

你的任務是確定啟動整個網路中每個站點所需的最少雷射脈衝數量，並提供一組滿足法律部門要求的路徑序列。

前兩個範例測試案例的圖示。請注意，在案例 2 中，第二個脈衝僅與第一個脈衝共享站點 2，滿足非干擾規則。

輸入格式

輸入包含多個測試案例。第一行包含一個整數 $T$ ($1 \le T \le 10^4$)，表示測試案例的數量。每個測試案例的格式如下：

第一行包含一個整數 $n$ ($2 \le n \le 3 \times 10^5$)，表示網格中的站點數量。

接下來的 $(n - 1)$ 行中，第 $i$ 行包含兩個整數 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，描述站點 $u_i$ 和站點 $v_i$ 之間的雙向光纖鏈路。

保證鏈路形成一棵樹，且所有測試案例的 $n$ 之和不超過 $3 \times 10^5$。

輸出格式

對於每個測試案例，第一行輸出最少路徑數量 $k$。接著輸出 $k$ 行，每行包含兩個整數 $a_i$ 和 $b_i$，代表序列中第 $i$ 條路徑的端點。請注意，如果路徑僅由單一站點組成，則 $a_i$ 可以等於 $b_i$。

若存在多個最佳序列，任何嚴格遵守非干擾協定的序列皆可被接受。

範例

輸入 1

3
3
1 2
2 3
5
1 2
2 3
2 4
2 5
7
1 2
1 3
2 4
2 5
3 6
3 7

輸出 1

1
1 3
2
4 5
1 3
3
7 7
1 6
4 5