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:
- Each node
must appear in exactly one tree.
- If an edge
exists in
, it must not exist in any of the constructed trees.
- 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
.
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.
Constraints
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
Comments