Optimizing Disease Containment

The outbreak of a certain infection exhibits two unusual properties:

• Its transmission route is tree‐shaped. In other words, a person \(X\) can be infected only by a specific person \(Y\). If the link \(XY\) is severed or \(Y\) does not fall ill, then \(X\) will remain healthy.
• The disease spreads in cycles. In one cycle the infection spreads only to the next generation (i.e. only the direct neighbors of currently infected individuals), and then it stops.

The health authority has obtained the potential transmission network of a susceptible population, which is given in the form of a tree. However, due to limited resources they are able to sever exactly one transmission edge per cycle. At the start only node 1 (the root) is infected. At each cycle, all edges from infected nodes to healthy nodes (called candidate edges) will propagate the disease simultaneously, except for the one edge that is cut by the control center. Severing (cutting) an edge disconnects the entire subtree from the infected portion, thereby saving all those nodes from infection. Once an edge is not cut in the cycle it immediately causes all nodes in its subtree to be infected, and no later counter‐action can save them.

Your task is to decide the order of cutting transmission edges (i.e. choosing one candidate edge in the very cycle it appears) to minimize the total number of infected persons.

Observation: Since initially only node 1 is infected, the candidate edges in cycle 1 are the edges connecting node 1 with its neighbors. You can only prevent infection in one branch per cycle. Thus, the optimal strategy is to cut the edge from node 1 to the neighbor whose subtree (if disconnected) has the maximum number of nodes. All other candidate edges will lead to immediate infection of their entire subtrees.

Once a branch is saved by cutting, it remains healthy forever. The final answer is the minimum total number of nodes that will be infected and the list of transmission edges (given as a pair of vertices) that should be cut in order. In this problem, the procedure will result in at most one cut since the only opportunity to prevent infection occurs in the first cycle from node 1.

Formally, if the tree (with \(n\) nodes) is rooted at node 1 and if for an edge \((1, v)\) the size of the subtree rooted at \(v\) is \(s_v\), then by cutting the edge \((1,v)\) you save \(s_v\) nodes and the final number of infected nodes is \(n - s_v\). Your goal is to choose the edge with the maximum \(s_v\) (if any exists) to minimize the number of infected individuals.

If node 1 has no children (i.e. \(n = 1\)), then the output should simply indicate that 1 node is infected and no edge is cut.

Note: The input tree is undirected. You should treat node 1 as the root (initially infected).

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), the number of nodes in the tree.

The next \(n-1\) lines each contain two integers \(u\) and \(v\) (\(1 \le u,v \le n\)), representing an undirected edge between nodes \(u\) and \(v\).

Assume that node 1 is the initially infected node (root of the tree).

outputFormat

On the first line, output a single integer: the minimum number of infected nodes after the optimal cut(s) have been made.

On the second line, output an integer \(k\) which denotes the number of transmission edges that are cut (this will be 0 if no cut is made, otherwise 1 in this problem).

If \(k > 0\), then output the next \(k\) lines, each containing two integers \(u\) and \(v\) representing the edge that was cut (where \(u\) is the infected node and \(v\) is the neighbor that is saved).

sample

1

1
0

</p>