Universal Cup Judging System

Universal Cup

Limite de temps : 3.0 s Limite de mémoire : 2048 MB Points totaux : 100 Difficulté: [afficher] Hackable ✓
Statistiques

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.