You command an army of moles. Your scouts have learned that humans are planning to hold a triathlon in your territory. You plan to have your army catch every last athlete in the race and drag them underground.
It is well known that a mole can easily catch a triathlete and drag them underground. The difficult part is figuring out where the athlete is.
The race venue is a tree with locations numbered from to , connected by paths. Every path has length . Let be the distance between locations and , measured along the unique route connecting them.
Before the race begins, you may station at most one mole at each location. The stationed moles will wait underground for an athlete to arrive.
Suppose an athlete is at one of the locations. By listening to the athlete's footsteps, a mole can determine the exact distance from its own location to the athlete's location. However, it cannot tell which direction the sound comes from. It can locate and catch the athlete only if exactly one location is at the measured distance.
Radios do not work underground, so the moles cannot communicate. Each mole must locate the athlete using only its own distance measurement, without using measurements from other moles.
Formally, a mole stationed at location can locate an athlete at location if the following holds for every location other than :
No matter which location the athlete occupies, at least one mole must be able to identify that location uniquely. Different moles may locate the athlete at different locations. A mole and the athlete may occupy the same location, in which case their distance is .
To conserve your army's strength, you want to deploy as few moles as possible. Find the minimum number of moles needed and the locations where they should be stationed. If several minimum deployments are possible, any one of them is acceptable.
The first line contains the number of test cases . The overall input format is:
For each test case, print two lines.
On the first line, print , the minimum number of moles needed so that an athlete at any location can be located.
On the second line, print distinct location numbers, separated by spaces. One mole is to be stationed at each of these locations.
The locations may be printed in any order. If several minimum deployments are possible, print any one of them.
In the first test case, station one mole at each of locations , , , , and .
If the athlete is at one of these five locations, the mole at that same location identifies them from distance . If the athlete is at location , the mole at location can locate them: location is the only location at distance from location . Similarly, the mole at location can locate an athlete at location from distance . Every possible location is covered, and the minimum number of moles is .
Each test case has the following format:
The first line contains , the number of locations at the race venue. Each of the next lines contains two location numbers and , indicating a path directly connecting them.
The given paths form a tree connecting all locations. If , there are no lines describing paths.
No vertex has degree . |
| 4 | 37 | No additional constraints. |
In the second test case, one mole at location is enough. It measures distances , , , and when the athlete is at locations , , , and , respectively. All four distances are different.
In the third test case, station one mole at the only location, .
In the first test case, station moles at locations , , and . An athlete at any of these three locations is located by the mole stationed there.
The mole at location can also locate an athlete at location from distance , or at location from distance . In each case, exactly one location is at that distance from location . Thus three moles cover every possible location. Locations , , and also form a valid minimum deployment.
In the second test case, suppose moles are stationed only at locations and . If the athlete is at location , both moles measure distance . However, the mole at location cannot distinguish locations and , while the mole at location cannot distinguish locations and . Since they cannot communicate, this deployment does not satisfy the requirement.
Stationing moles at all three locations , , and allows each of those locations to be identified from distance . An athlete at location can also be located by the mole at location from distance .
