G. Пути через вершину

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

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

Формат ввода

В первой строке - числа $N$ и $M$ ( $0 \le N, M \le 10^5$ ).

В следующих $M$ строках - рёбра. Граф неориентирован и ацикличен.

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

Выведите $N$ чисел - для каждой вершины количество простых путей через неё.

Примеры

ввод

3 2
1 2
2 3

вывод

2 3 2

ввод

вывод

2 3 2 1 1

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.