Universal Cup Judging System

Universal Cup

Time Limit: 3.0 s Memory Limit: 2048 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

Piggy(在業餘時間負責管理星際互聯協議委員會)正面臨一個棘手的硬體難題。最新的通訊網格由 $n$ 個中繼站透過 $(n - 1)$ 條光纖鏈路連接成樹狀結構,終於準備就緒即將部署。然而,系統的通電啟動必須極度謹慎。

啟動過程需要沿著特定路徑發射雷射脈衝。一條路徑定義為兩個站點之間唯一的簡單路徑。由於存在「量子回流干擾」(一種讓委員會法務部門徹夜難眠的現象)的災難性風險,必須嚴格遵守以下協議:

  • 傳輸路徑必須逐一建立。
  • 為防止功率驟增,每條新建立的路徑與先前任何路徑已啟動的站點集合之間,至多只能共用一個站點。

形式化地說,設 $S$ 為目前已經啟動的站點集合。對於任意由站點集合 $V(P)$ 組成的新路徑 $P$,必須滿足條件 $|V(P) \cap S| \le 1$。一旦一條路徑成功發射脈衝,該路徑上的所有站點都將被視為已加入啟動集合 $S$。

你的任務(如果你選擇接受的話)是決定啟動整個網路中每個站點所需的最少雷射脈衝次數,並提供一組滿足法務部門要求的路徑序列。

problem_16337_7ea995da1220bc7e6a98609de7d2cace.png
前兩組範例測試資料的示意圖。注意在情況 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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.