activity with her tree, as long as she really wants: Eliminate any current edge. Add an edge between any pair of vertices. What is the base number of activities Nastia needs to get a bamboo from a tree? A bamboo is a tree
Correct answer will be upvoted else downvoted.
The young lady will play out the accompanying activity with her tree, as long as she really wants:
Eliminate any current edge.
Add an edge between any pair of vertices.
What is the base number of activities Nastia needs to get a bamboo from a tree? A bamboo is a tree where no hub has a degree more noteworthy than 2.
Input
The main line contains a solitary integer t (1≤t≤10000) — the number of experiments.
The main line of each experiment contains a solitary integer n (2≤n≤105) — the number of vertices in the tree.
Next n−1 lines of each experiments portray the edges of the tree in structure simulated intelligence, bi (1≤
It's dependable the given diagram is a tree and the amount of n in one test doesn't surpass 2⋅105.
Output
For each experiment in the main line print a solitary integer k — the base number of activities needed to get a bamboo from the underlying tree.
In the following k lines print 4 integers x1, y1, x2, y2 (1≤x1,y1,x2,y2≤n, x1≠y1, x2≠y2) — this way you eliminate the edge (x1,y1) and add an undirected edge (x2,y2).
Step by step
Solved in 3 steps with 1 images
