В Берляндии есть n городов и n - 1 дорога с двусторонним движением. Каждая дорога соединяет какую-то пару городов, при этом от любого города можно доехать до любого другого, используя только данные дороги.
В каждом городе есть ровно одна ремонтная бригада. Чтобы отремонтировать какую-то дорогу, необходима одновременная работа в течение одного дня двух бригад, базирующихся в городах, которые эта дорога соединяет. Обе бригады занимаются ремонтом одной дороги весь день и не могут в этот день участвовать в ремонте других дорог, а вот ничего не делать в течение дня ремонтная бригада вполне может.
Определите минимальное количество дней, в течение которых можно отремонтировать все дороги. Бригады не могут менять города, в которых расположены изначально.
Выходные данные
Сначала выведите число k — минимальное количество дней, за которое возможно отремонтировать все дороги Берляндии.
В следующих k строках выведите описание дорог, которые должны быть отремонтированы в каждый из k дней. В i-й строке выведите сначала число di — количество дорог, которые должны быть отремонтированы в i-й день, а затем через пробел выведите di целых чисел — номера дорог, которые должны быть отремонтированы в i-й день. Дороги нумеруются согласно порядку во входных данных, начиная с единицы.
Если вариантов ответа несколько, разрешается вывести любой из них.
Примечание
В первом примере отремонтировать все дороги можно за два дня, например, отремонтировать дороги 1 и 2 в первый день, а дорогу 3 — во второй.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2
3 4
3 2
|
2
2 2 1
1 3
|
|
2
|
6
3 4
5 4
3 2
1 3
4 6
|
3
1 1
2 2 3
2 4 5
|