Bus Routes

A city's road network is a tree made of points and roads, as shown below.

Each point is shown as a numbered circle, and each line between two points is a road. The network has the following properties.

• From any point, every other point is reachable by following roads.
• It is impossible to start from a point and return to it without using some road at least twice.
• At most 10 roads meet at any point.

You want to create several bus routes on this network. Each route is a simple path from one terminal to another. A terminal must be a leaf point, meaning a point connected to exactly one road.

The routes must satisfy all of the following conditions.

• Every point must belong to at least one route. A point may belong to multiple routes.
• Every road must belong to exactly one route. The same road cannot be used by two different routes.
• Both ends of every route must be leaf points, and a route must not visit the same point or road twice.
• Among all route sets satisfying the conditions above, the length of the longest route must be as small as possible. Every road has length 1.

For Figure 1, three routes can be chosen, and the longest route has length 4.

There are also cases, such as the figure below, where no route set satisfies the conditions.

Given a tree road network, write a program that outputs bus routes satisfying the conditions while minimizing the longest route length.

The first line contains the number of points n. (2 <= n <= 500)

Each of the next n - 1 lines contains one road. If there is a road between points i and j, the line is written as either i j or j i. Point numbers are distinct integers from 1 to n.

If a valid set of routes exists, print the length of the longest route on the first line. Print the number of routes m on the second line.

Then print m lines, one route per line. A route line lists the point numbers visited from one terminal to the other, in order. Separate adjacent numbers with one space.

If there are multiple valid answers, print any one of them.

If no valid set of routes exists, print 0 on the first line.