D. Вершина Прюфера
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для дерева $$$T$$$ с $$$n \ge 2$$$ вершинами рассмотрим стандартный процесс генерации его кода (последовательности) Прюфера. Мы многократно выполняем следующие шаги, пока не останется только две вершины:

  • Выберите лист с наименьшим номером;
  • Удалите его из дерева.

Известно, что вершина $$$n$$$ всегда является одной из двух оставшихся вершин. Пусть $$$v$$$ — другая оставшаяся вершина. Мы определяем вершину Прюфера дерева $$$T$$$ как $$$P(T) = v$$$.

Вам дан лес с $$$n$$$ вершинами и $$$m$$$ рёбрами. Пусть $$$k$$$ — количество связанных компонент в этом лесу, а их размеры равны $$$s_1, s_2, \ldots, s_k$$$. Известно, что существует ровно $$$n^{k - 2} \prod\limits_{i=1}^k s_i$$$ способов добавить рёбра в лес, чтобы он стал единым деревом.

Для каждой вершины $$$v$$$ ($$$1 \le v \lt n$$$) вычислите, сколько из этих способов приводят к дереву $$$T$$$, удовлетворяющему условию $$$P(T) = v$$$.

Поскольку ответы могут быть большими, выведите их по модулю $$$998\,244\,353$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le n - 1$$$) — количество вершин и рёбер в лесу соответственно.

Следующие $$$m$$$ строк каждого набора входных данных содержат по два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n, u \neq v$$$), описывающих ребро между вершинами $$$u$$$ и $$$v$$$. Гарантируется, что эти рёбра образуют лес (то есть граф ацикличен).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n - 1$$$ целых числа в одной строке. $$$i$$$-е число должно быть количеством способов добавить рёбра в лес, чтобы он стал деревом $$$T$$$, удовлетворяющим условию $$$P(T) = i$$$, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
3
3 0
5 4
4 2
3 4
1 2
4 5
6 3
1 6
6 4
2 1
Выходные данные
1 2 
0 0 0 1 
12 0 1 6 5
Примечание

В первом наборе входных данных в лесу нет рёбер, и существует $$$3$$$ способа дополнить его до дерева. Один из них — добавить рёбра $$$(1, 2)$$$ и $$$(1, 3)$$$. Существует $$$2$$$ листа: вершины $$$2$$$ и $$$3$$$. Поскольку $$$2$$$ имеет меньший номер, она удаляется из дерева, и остаются только две вершины: $$$1$$$ и $$$3$$$. Следовательно, вершина Прюфера этого дерева равна $$$1$$$.

В третьем наборе входных данных лес показан ниже:

Предположим, что мы добавим рёбра $$$(3, 5)$$$ и $$$(3, 1)$$$, чтобы дополнить его до дерева $$$T$$$. Оно будет выглядеть так:

Можно показать, что $$$P(T) = 1$$$.