Берляндия смогла отразить удар флатландцев и теперь переходит в наступление.
Во Флатландии n городов, пронумерованных от 1 до n, и некоторые пары из них соединены двухсторонними дорогами. Флатландцы (то ли это их военная хитрость, а может, они просто экономят чернила) на своих картах соединяют дорогой те и только те города, между которыми на самом деле нет дороги. Другими словами, если на карте флатландцев два города соединены дорогой, значит на самом деле между ними дороги нет. Обратное тоже верно: если на карте флатландцев два города не соединены дорогой, значит на самом деле дорога между ними есть.
В руки берляндцев попала флатландская карта. Теперь ефрейтор Вася по заданию генерала Туристова хочет найти все такие группы флатландских городов, что в каждой группе из каждого города можно попасть в каждый, двигаясь по настоящим дорогам, при этом города из разных групп недостижимы по настоящим дорогам. Действительно, разгромить такие группы по отдельности значительно легче, чем окружать сразу всю Флатландию!
Помогите ефрейтору выполнить это задание и получить-таки звание сержанта! Не забудьте, что на флатландской карте города, соединены дорогой тогда и только тогда, когда на самом деле между ними нет дороги.
В первой строке записано два целых числа через пробел n и m (1 ≤ n ≤ 5·105, 0 ≤ m ≤ 106) — количество городов и количество дорог, обозначенных на флатландской карте, соответственно.
В следующих m строках записаны описания дорог на карте. В i-ой строке записано два целых числа ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — номера городов, которые соединяет i-я дорога на карте флатландцев.
Гарантируется, что каждая пара городов встречается во входных данных не больше одного раза.
Выведите в первой строке число k — количество групп городов во Флатландии таких, что в каждой группе из каждого города можно добраться до каждого по дорогам Флатландии, а города разных групп недостижимы по флатландским дорогам.
В каждой из следующих k строк выведите сначала ti (1 ≤ ti ≤ n) — количество вершин в i-й группе. Далее через пробел выведите номера городов i-й группы.
Порядок вывода групп и порядок вывода номеров в группах значения не имеет. Сумма ti по всем k группам должна быть равна n.
4 4
1 2
1 3
4 2
4 3
2
2 1 4
2 2 3
3 1
1 2
1
3 1 2 3
В первом примере есть только дороги между парами городов 1-4 и 2-3.
Во втором примере между городами 1 и 2 нет дороги, но все равно можно добраться из одного до другого через город номер 3.
| Codeforces Round 120 (Div. 2) |
|---|
| Закончено |
