## An Animal Contest 7 P2 - Squirrel Structures

View as PDF

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

Author:
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 nodes and edges with the property that for every pair where , there is exactly one path from to .

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

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

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

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

#### Input Specification

The first line of input contains a single integer .

The next lines of input contain space separated integers and denoting an edge between and in .

#### Output Specification

The first line of output will contain a single integer , 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 , the number of nodes in the tree.

Then, output lines that contain space separated integers and denoting an edge between and .

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.

#### Scoring

For each test case:

• If you output the minimal but output an invalid set of trees you will receive 50% of the points.
• If you output the minimal 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

5
1 2
2 3
2 4
4 5

#### Sample Output

2
3
1 3
1 4
2
2 5