你有一个具有以下性质的无向图： 对于图中任意 7 个顶点的子集 $A$，都存在两个顶点 $a, b \in A$ 以及一个顶点 $c \notin A$，使得从 $a$ 到 $b$ 的所有路径都经过顶点 $c$。

你需要求出用 $1, 2, \dots, n$ 种颜色对该图进行合法染色的方案数，结果对 $998\,244\,353$ 取模。 图的 $k$ 染色是指为每个顶点分配一个 $1$ 到 $k$ 之间的整数颜色。如果每条边的两个端点颜色不同，则称该染色是合法的。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示图的顶点数和边数 ($1 \le n, m \le 10^5$)。 接下来 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$，描述一条连接顶点 $a_i$ 和 $b_i$ 的边 ($1 \le a_i, b_i \le n, a_i \neq b_i$)。图中不存在重边。

题目保证：对于图中任意 7 个顶点的子集 $A$，都存在两个顶点 $a, b \in A$ 以及一个顶点 $c \notin A$，使得从 $a$ 到 $b$ 的所有路径都经过顶点 $c$。

输出格式

输出一行，包含 $n$ 个用空格分隔的整数。第 $i$ 个整数表示用 $i$ 种颜色对该图进行合法染色的方案数，结果对 $998\,244\,353$ 取模。

样例

样例输入 1

5 3
3 5
5 1
1 3

样例输出 1

0 0 54 384 1500