Однажды одна из команд довольно неклассического университета участвовала в сборах по программированию. На одном из контестов была предложена задача с довольно большим условием, которое принялись одновременно читать двое из трех участников команды — гроссмейстер-геометр Захар и специалист в области ASCII-графики и парсеров Майк. Через некоторое время ребята прочитали условие, обсудили его и выяснили, что задача является довольно простой, и через пятнадцать минут решение уже было готово и отправлено в тестирующую систему. Однако, по какой-то причине, команду ожидала неудача — «Неправильный ответ на тесте 4».

Майк и Захар обсудили решение, после чего их недоумение лишь возросло, так как они были уверены в правильности написанного кода. После этого Захар решил еще раз прочитать условие задачи, и оказалось, что написанный код действительно решал задачу... Только вот совсем другую, из-за того, что условие было прочитано невнимательно.

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

Дан неориентированный граф, состоящий из $$$n$$$ вершин и $$$m$$$ ребер, соединяющих некоторые пары вершин.

Назовем последовательность вершин $$$v_1, v_2, \ldots, v_k$$$ простым путем, если для любых $$$i \neq j$$$ верно, что $$$v_i \neq v_j$$$, а также для любого $$$i = 1 \ldots k - 1$$$ в графе есть ребро, соединяющее вершины $$$v_i$$$ и $$$v_{i + 1}$$$.

Длиной простого пути будем считать количество вершин в нем.

Два простых пути $$$v_1, v_2, \ldots, v_k$$$ и $$$u_1, u_2, \ldots, u_l$$$ считаются различными, если $$$k \neq l$$$, либо $$$k = l$$$ и существует такое $$$i$$$, что $$$v_i \neq u_i$$$.

Назовем три различных простых пути $$$3$$$-связанными, если выполнены следующие условия:

1. Первые вершины путей совпадают;
2. Последние вершины путей совпадают;
3. Если рассмотреть множество всех вершин данных путей, за исключением первой и последней, то найдется вершина, которая встречается более, чем в одном из трех путей.

Обратите внимание, что $$$3$$$-связанные пути не обязаны иметь одинаковую длину.

Про данный граф известно, что в нем невозможно выбрать три различных простых $$$3$$$-связанных пути.

Требуется для каждого $$$l = 1 \ldots n$$$ вычислить количество различных простых путей длины $$$l$$$ в данном графе.