CF1521D Nastia Plays with a Tree

Nastia 有一棵无权树，包含 $n$ 个顶点，她想用这棵树来玩游戏！ 她会对她的树进行如下操作，次数不限： 1. 移除任意一条已存在的边。 2. 在任意一对顶点之间添加一条边。 Nastia 至少需要进行多少次操作，才能将树变成“竹子”？“竹子”是一种树，其中没有任何节点的度数大于 $2$。

第一行包含一个整数 $t$（$1 \le t \le 10\,000$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^5$），表示树的顶点数。 接下来的 $n-1$ 行，每行描述树中的一条边，形式为 $a_i$，$b_i$（$1 \le a_i, b_i \le n$，$a_i \neq b_i$）。 保证给定的图是一棵树，且单个测试用例中所有 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，第一行输出一个整数 $k$，表示将初始树变成竹子所需的最小操作次数。 接下来的 $k$ 行，每行输出 $4$ 个整数 $x_1$、$y_1$、$x_2$、$y_2$（$1 \le x_1, y_1, x_2, y_2 \le n$，$x_1 \neq y_1$，$x_2 \neq y_2$），表示移除边 $(x_1, y_1)$ 并添加无向边 $(x_2, y_2)$。 注意，移除的边 $(x_1, y_1)$ 必须在操作时存在于图中。

注意，在某些操作后，图可能会变成不连通的。 考虑样例的第一个测试用例：  红色的边被移除，绿色的边被添加。 由 ChatGPT 4.1 翻译