Nastia Plays with a Tree
Contest: Codeforces Round 720 (Div. 2)
Difficulty rating: 2500
Tags: constructive algorithms, data structures, dfs and similar, dp, dsu, greedy, implementation, trees

Nastia has an unweighted tree with $$$n$$$ vertices and wants to play with it!

The girl will perform the following operation with her tree, as long as she needs:

1. Remove any existing edge.
2. Add an edge between any pair of vertices.

What is the minimum number of operations Nastia needs to get a bamboo from a tree? A bamboo is a tree in which no node has a degree greater than $$$2$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of vertices in the tree.

Next $$$n - 1$$$ lines of each test cases describe the edges of the tree in form $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \neq b_i$$$).

It's guaranteed the given graph is a tree and the sum of $$$n$$$ in one test doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case in the first line print a single integer $$$k$$$ — the minimum number of operations required to obtain a bamboo from the initial tree.

In the next $$$k$$$ lines print $$$4$$$ integers $$$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$$$) — this way you remove the edge $$$(x_1, y_1)$$$ and add an undirected edge $$$(x_2, y_2)$$$.

Note that the edge $$$(x_1, y_1)$$$ must be present in the graph at the moment of removing.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
Note the graph can be unconnected after a certain operation.

Consider the first test case of the example:

Example input:
2
7
1 2
1 3
2 4
2 5
3 6
3 7
4
1 2
1 3
3 4

Example output:
2
2 5 6 7
3 6 4 5
0

Editorial:
Let's define the variable $$$x$$$ as a minimum number of operations that we need to get bamboo from a tree.
Let's remove $$$x$$$ edges first and then add $$$x$$$ new ones to the graph.
Consider the structure of the graph after removing $$$x$$$ edges. This is a forest with a $$$x + 1$$$ connected components.
Easy to notice each of the $$$x + 1$$$ connected components in the getting forest of trees must be a bamboo to get the bamboo after adding new $$$x$$$ edges.
Thus, we can get the bamboo from the forest of bamboo after removing $$$x$$$ edges by $$$x$$$ times adding the conjunction between leaves that are in the different components of connectivity of the forest.
So, the task is to find the minimum number of the removing edges needs to get the forest of bamboos. Here works the following greedy:
Let's define any vertice of the tree as a root.
We will solve the problem for each of the subtrees $$$v$$$ $$$(1 \le v \le n)$$$.
First, solve the problem for all child vertices of $$$v$$$. Then define the value $$$c_v$$$ as the number of the children and the value $$$p_v$$$ as the ancestor for vertex $$$v$$$.
There are $$$3$$$ cases:
1. If $$$c_v <= 1$$$, then we don't remove anything.
2. If $$$c_v = 2$$$, then we remove the edge $$$(p_v, v)$$$ if $$$p_v$$$ exists.
3. If $$$c_v > 2$$$, then we remove the edge $$$(p_v, v)$$$ if $$$p_v$$$ exists and any $$$c - 2$$$ existing edges from $$$v$$$ to one of the children vertex.
Take a look at the picture: