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.

Constraints

~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.

Scoring

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

5
1 2
2 3
2 4
4 5

Sample Output

2
3
1 3
1 4
2
2 5