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$。
若存在多組最佳序列,輸出任意一組嚴格遵守無干擾協議的方案皆可被接受。
範例
輸入
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 3 2 4 5 1 3 3 7 7 1 6 4 5