Universal Cup Judging System

Universal Cup

时间限制: 3.0 s 内存限制: 2048 MB 总分: 100 难度: [显示] 可 Hack ✓
统计

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.