Universal Cup Judging System

Universal Cup

시간 제한: 3.0 s 메모리 제한: 2048 MB 총점: 100 난이도: [표시] 해킹 가능 ✓
통계

ピギー(余暇には恒星間接続プロトコル委員会を運営している)は、繊細なハードウェアの難問に直面しています。$n$ 個の中継局を $(n - 1)$ 本の光ファイバーリンクで木構造になるよう接続した最新の通信グリッドがついに配備準備を整えました。しかし、システムの電源投入は細心の注意を払って行わなければなりません。

起動プロセスでは、特定のパスに沿ってレーザーパルスを発射します。パスとは、$2$ つの局を結ぶ一意な単純道として定義されます。委員会の顧問弁護士たちを夜も眠れなくさせる現象「量子逆流干渉(Quantum Backflow Interference)」の壊滅的なリスクを避けるため、以下のプロトコルを厳守しなければなりません:

  • 伝送パスは $1$ 本ずつ順番に確立しなければならない。
  • 電力サージを防ぐため、新たに確立する各パスは、それ以前のパスによってすでに起動された局の集合と高々 $1$ つの局しか共有してはならない。

形式的には、現在起動されている局の集合を $S$ とします。局の集合 $V(P)$ からなる新しいパス $P$ について、条件 $|V(P) \cap S| \le 1$ が成り立たなければなりません。パスに沿ってパルスが発射されると、そのパス上のすべての局は起動済み集合 $S$ の一部とみなされます。

あなたの使命は、ネットワーク内のすべての局を起動するために必要なレーザーパルスの最小回数を求め、法務部門を納得させるようなパスの列を $1$ つ示すことです。

problem_16337_7ea995da1220bc7e6a98609de7d2cace.png
最初の $2$ つのサンプルテストケースの図解。Case 2 では、$2$ 回目のパルスが $1$ 回目と局 $2$ のみを共有しており、非干渉ルールを満たしていることに注意してください。

入力

複数のテストケースが与えられます。入力の $1$ 行目には、テストケースの数を表す整数 $T$($1 \le T \le 10^4$)が与えられます。各テストケースについて:

$1$ 行目には、グリッド内の局の数を表す整数 $n$($2 \le n \le 3 \times 10^5$)が与えられます。

続く $(n - 1)$ 行のうち $i$ 行目には、$2$ つの整数 $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$ を超えないことが保証されます。

出力

各テストケースについて、まず $1$ 行目にパスの最小本数 $k$ を出力してください。続いて $k$ 行を出力し、その $i$ 行目には列の $i$ 番目のパスの両端点を表す $2$ つの整数 $a_i$ と $b_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.