An Animal Contest 7 P2 - Squirrel Structures

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

After learning about the impending squirrel invasion, the AAC (Alliance Against Catastrophes) intelligence agency sent Julian to scout out the depths of the squirrel armada (in a pocket of space far, far away). Unfortunately, Julian was discovered on the way back from his scouting mission by the vigilant squirrel guard. After poking the squirrels nest, Julian must now escape a horde of enraged squirrels. He has just made it outside, and needs to find a way to partition his rest stops so he can make it home safely...

A tree is an undirected connected graph with N nodes and N - 1 edges with the property that for every pair (i, j) where 1 \le i, j \le N, there is exactly one path from i to j.

There is a tree A with N nodes rooted at 1. You must construct a set of K trees that satisfy the following constraints:

  1. Each node i (1 \le i \le N) must appear in exactly one tree.
  2. If an edge (u, v) exists in A, it must not exist in any of the constructed trees.
  3. There must be at least one possible root choice for each tree B, such that if 2 nodes u and v are in B, u is an ancestor of v in B if and only if u is an ancestor of v in A.
  4. K must be minimal amongst all trees that satisfy the first three constraints.

In a rooted tree, u is an ancestor of v if u is on the unique path from v to the root.

"A if and only if B" means that either A and B are both true or they are both false.


1 \le N \le 2 \times 10^5

Input Specification

The first line of input contains a single integer N.

The next N - 1 lines of input contain 2 space separated integers u_i and v_i denoting an edge between u_i and v_i in A.

Output Specification

The first line of output will contain a single integer K (1 \le K \le N), the number of trees you will construct.

You will output each tree one at a time.

For each tree, first output a line containing a single integer M_i, the number of nodes in the tree.

Then, output M_i - 1 lines that contain 2 space separated integers x_i and y_i denoting an edge between x_i and y_i.

You may output the trees in any order, the edges in each tree in any order, and the label of the edges in any order.


For each test case:

  • If you output the minimal K but output an invalid set of trees you will receive 50% of the points.
  • If you output the minimal K and output a valid set of trees you will receive 100% of the points.

Your final score is the minimum score over all test cases.

Sample Input

1 2
2 3
2 4
4 5

Sample Output

1 3
1 4
2 5


There are no comments at the moment.