In Berland there are n cities and n - 1 bidirectional roads. Each road connects some pair of cities, from any city you can get to any other one using only the given roads.

In each city there is exactly one repair brigade. To repair some road, you need two teams based in the cities connected by the road to work simultaneously for one day. Both brigades repair one road for the whole day and cannot take part in repairing other roads on that day. But the repair brigade can do nothing on that day.

Determine the minimum number of days needed to repair all the roads. The brigades cannot change the cities where they initially are.


-----Input-----

The first line of the input contains a positive integer n (2 ≤ n ≤ 200 000) — the number of cities in Berland.

Each of the next n - 1 lines contains two numbers u_{i}, v_{i}, meaning that the i-th road connects city u_{i} and city v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}).


-----Output-----

First print number k — the minimum number of days needed to repair all the roads in Berland.

In next k lines print the description of the roads that should be repaired on each of the k days. On the i-th line print first number d_{i} — the number of roads that should be repaired on the i-th day, and then d_{i} space-separated integers — the numbers of the roads that should be repaired on the i-th day. The roads are numbered according to the order in the input, starting from one.

If there are multiple variants, you can print any of them.


-----Examples-----
Input
4
1 2
3 4
3 2

Output
2
2 2 1
1 3

Input
6
3 4
5 4
3 2
1 3
4 6

Output
3
1 1 
2 2 3 
2 4 5 



-----Note-----

In the first sample you can repair all the roads in two days, for example, if you repair roads 1 and 2 on the first day and road 3 — on the second day.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Graph algorithms

Graph traversal

Greedy algorithms


Solutions:
import sys
import threading
from collections import defaultdict

def put():
	return map(int, input().split())

def dfs(i, p, m):
	cnt = 1
	z = 0
	for j in tree[i]:
		if j == p:
			continue
		if cnt == m:
			cnt += 1
		index = edge_index[i, j]
		ans[cnt].append(index)
		z = max(dfs(j, i, cnt), z)
		cnt += 1
	return max(z, cnt - 1)

def solve():
	l = dfs(1, 0, 0)
	print(l)
	for i in range(1, l + 1):
		print(len(ans[i]), *ans[i])
n = int(input())
edge_index = defaultdict()
ans = [[] for i in range(n + 1)]
tree = [[] for i in range(n + 1)]
for i in range(n - 1):
	(x, y) = put()
	edge_index[x, y] = i + 1
	edge_index[y, x] = i + 1
	tree[x].append(y)
	tree[y].append(x)
max_recur_size = 10 ** 5 * 2 + 1000
max_stack_size = max_recur_size * 500
sys.setrecursionlimit(max_recur_size)
threading.stack_size(max_stack_size)
thread = threading.Thread(target=solve)
thread.start()