Задача L. Социальная сеть ≡

Условие

Программист Вася написал собственную социальную сеть и позвал туда своих друзей, которые охотно согласились принять участие в его проекте.

Как и в любой другой подобной сети каждый пользователь может приглашать новых участников и добавлять к себе в друзья других пользователей.

Спустя некоторое время Вася захотел написать программу, позволяющую расширить круг его знакомств на основе существующих связей. Для этого он ввел в рассмотрение метрику, разделяющую пользователей сети на несколько последовательных слоев.

Первый слой знакомств включает в себя только тех пользователей с которыми его связывают отношения дружбы. Каждый последующий слой включает в себя пользователей, не вошедших в предыдущие слои, но имеющих связи с их участниками.

Требуется вывести всех пользователей такой сети по мере удаления от Васи, записав их в виде набора последовательных слоев (начиная с 1-го).

Формат входного файла

В начале входного файла "input.txt" содержится натуральное N — число пользователей в сети.

Далее следует натуральное M после которого идет набор из M записей (A_i, B_i), где A_i и B_i — номера пользователей, связанных отношением дружбы.
При этом полагается, что нумерация пользователей начинается с нуля, где 0 — номер Васи.

Формат выходного файла

Выходной файл "output.txt" должен содержать полученные слои, расположенные в порядке удаленности от Васи и записанные в следующем виде.

Вначале указывается число пользователей, формирующих текущий слой.
Далее записываются их номера (в произвольном порядке).

Ограничения

2 ≤ N ≤ 1000, 1 ≤ M ≤ (N ⋅ (N − 1)) / 2,

A_i ≠ B_i

Примеры тестов

10 12
0 1
0 2
0 3
2 4
3 5
3 6
5 6
6 7
4 8
7 4
1 9
4 3

3 2 3 1
4 9 4 5 6
2 7 8