Однажды Бернард и Рудольф прогуливались по лесу. Как истинные алгоритмические программисты, они начали составлять модели попадавшихся им деревьев. Это оказалось не такой сложной задачей. Ведь основным отличием разных видов являются листья.
Лес оказался очень разнообразным. Поэтому, придя домой, Бернард и Рудольф немедленно занесли все данные в компьютер.
Они представили каждое дерево как связный неориентированный граф без циклов и петель с $$$L$$$ вершинами и $$$L - 1$$$ ребром. Затем к каждому листу соответствующего дерева они подвесили графы, характеризующие листья реальных деревьев. В их модели лист представляет собой простой цикл определенной длины не менее $$$3$$$ (контур листа), вершины которого могут быть соединены произвольным образом (жилы листа). Все листья одного дерева имеют одинаковый размер цикла.
Занеся все данные, Рудольф и Бернард задались вопросом, а сколько каких видов деревьев они обозначили. А вы сможете ответить на этот вопрос?
Первая строка содержит целые числа $$$N$$$ и $$$M$$$ ($$$6 \le N \le 10^6, 7 \le M \le 5 \cdot 10^6$$$) — количество вершин и ребер модели леса соответственно.
Далее следует $$$M$$$ строк, каждая из которых содержит по два числа $$$U$$$ и $$$V$$$ ($$$1\le U, V \le N, U \neq V$$$) — вершины, соединенные неориентированным ребром.
Гарантируется, что каждое дерево леса имеет хотя бы две вершины.
В первой строке выведите целое число $$$K$$$ — количество видов деревьев в лесу. Далее во второй строке выведите $$$K$$$ целых чисел через пробел — количество деревьев каждого вида в порядке возрастания.
| Группа | Доп. ограничения | Баллы | Требуемые подзадачи | Тип проверки |
| $$$1$$$ | В лесу деревья одного типа | $$$10$$$ | — | Полная |
| $$$2$$$ | Все листья не имеют жилок | $$$30$$$ | $$$1$$$ | Полная |
| $$$3$$$ | — | $$$60$$$ | $$$2$$$ | Каждый тест |
22 26 1 2 2 6 6 7 2 7 1 3 3 4 3 5 4 8 8 9 9 4 10 5 10 11 5 11 12 13 13 17 17 18 13 18 12 14 14 15 14 16 15 19 19 20 20 15 21 16 21 22 16 22
1 2
9 12 1 7 7 8 8 9 1 9 1 2 2 3 3 4 3 5 3 6 4 5 4 6 5 6
1 1
Лес из второго примера изображен на рисунке. В нем одно дерево с двумя листьями размера 4.
