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