← 返回题目列表

Codeforces · 1521/D

D. 娜斯蒂亚玩树

中文机器翻译题面 查看原题

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)$$$ 必须在删除时出现在图中。

示例

输入 #1

2
7
1 2
1 3
2 4
2 5
3 6
3 7
4
1 2
1 3
3 4

输出 #1

2
2 5 6 7
3 6 4 5
0

注意

请注意,在执行特定操作后,图形可能会断开连接。

考虑示例的第一个测试用例: