EduBrick

O. Размеры слоёв

3000 мс · 256 МБ · всё или ничего

Неориентированный граф задан списком рёбер. Обход в ширину из вершины 1 разбивает достижимые вершины на слои: слой dd — все вершины на расстоянии dd.

Выведите размеры всех непустых слоёв по порядку.

Эти числа — самая наглядная картина того, как устроен граф: у цепочки все слои по единице, у звезды слоёв всего два.

Формат ввода

Первая строка содержит числа nn (1≤n≤1051 \le n \le 10^5) и mm (0≤m≤2⋅1050 \le m \le 2 \cdot 10^5).

Далее идут mm строк с рёбрами.

Формат вывода

В первой строке — количество непустых слоёв.

Во второй — их размеры по порядку.

Примеры

ввод
5 4
1 2
1 3
2 4
3 5
вывод
3
1 2 2
ввод
6 5
1 2
1 3
1 4
1 5
1 6
вывод
2
1 5
Войдите, чтобы отправлять решения.