题目描述

给定一个简单无向图 $G$，它具有 $N$ 个顶点和 $M$ 条边。顶点编号为 $1,2,\\dots,N$，边的编号为 $1,2,\\dots,M$，第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。
考虑从 $G$ 中删除零条或多条边以得到一个新图 $H$。我们可以得到 $2^M$ 个作为 $H$ 的图。其中找出满足对于每个整数 $k$（$2 \\leq k \\leq N$），顶点 $1$ 和顶点 $k$ 是直接或间接相连的这样的图的数量。
由于计数可能非常大，将结果对 $998244353$ 取模后输出。

约束条件

• $2 \\leq N \\leq 17$
• $0 \\leq M \\leq \\frac{N(N-1)}{2}$
• $1 \\leq a_i \\lt b_i \\leq N$
• 当 $i \\neq j$ 时，$(a_i, b_i) \\neq (a_j, b_j)$。
• 输入中的所有值都是整数。

输入

输入是标准输入给出的以下格式：

$N$ $M$ $a_1$ $b_1$ $\\vdots$ $a_M$ $b_M$

输出

打印 $N-1$ 行。第 $i$ 行应该包含 $k = i + 1$ 时的答案。

示例输入 1

3 2
1 2
2 3

示例输出 1

2
1

我们可以得到以下作为 $H$ 的图。

• 没有边的图。顶点 $1$ 与任何其他顶点都没有连接。
• 只有连接顶点 $1$ 和顶点 $2$ 的边的图。顶点 $2$ 可以从顶点 $1$ 到达。
• 只有连接顶点 $2$ 和顶点 $3$ 的边的图。顶点 $1$ 与任何其他顶点都没有连接。
• 两条边都存在的图。顶点 $2$ 和顶点 $3$ 可以从顶点 $1$ 到达。

示例输入 2

5 6
1 2
1 4
1 5
2 3
2 5
3 4

示例输出 2

43
31
37
41

示例输入 3

2 0

示例输出 3

0