You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

希望大家一直记得我。

“希望大家永远忘了我。”

题目描述

有一个 $n$ 个节点、$m$ 条边的无向图 $G$，节点由 $1$ 至 $n$ 编号。第 $i$（$1 \leq i \leq m$）条边连接 $u_i$ 和 $v_i$。保证 $G$ 无重边、自环。

小 I 预见到岁月将会磨灭图 $G$ 的痕迹，而这导致小 I 只能记忆住一个长度为 $n - 1$ 的 $\texttt{01}$ 串。小 I 还记得这个 $\texttt{01}$ 串 $s$ 的生成方式：有一个长度为 $n$ 的 $1 \sim n$ 的排列 $p_1 \dots p_n$，则对每个 $1 \leq k \leq n - 1$，若 $p_k, p_{k+1}$ 之间有边，那么 $s_k = \tt 1$；否则 $s_k = \tt 0$。

小 I 希望图的核心历经岁月侵蚀也保持不变，所以对于所有 $2^{n-1}$ 种 $s$，请你求出：若排列 $p$ 在所有可能的排列中随机，则生成的 $\texttt{01}$ 串恰好为 $s$ 的概率。答案对 $99824353$ 取模。

输入格式

从 years.in 中读入数据。

第一行，两个整数 $n, m$。

接下来 $m$ 行，第 $i$ 行有两个整数 $u_i, v_i$。

输出格式

输出到 years.out 中。

一行 $2^{n-1}$ 个整数，按照 $s$ 字典序从小到大的顺序，依次表示生成每个 $s$ 的概率，对 $998244353$ 取模后的结果。

样例

3 1
1 2

332748118 332748118 332748118 0

样例 1 解释

选取 $1 \sim 3$ 的 $6$ 种不同排列，$[1, 2, 3], [2, 1, 3]$ 对应 $\tt 10$，$[1, 3, 2], [2, 3, 1]$ 对应 $\tt 00$，$[3, 1, 2], [3, 2, 1]$ 对应 $\tt 01$。容易发现 $\tt{00, 01, 10}$ 每种出现概率相等，均为 $\frac 13$，而 $\frac 13 \equiv 332748118 \pmod{998244353}$。

附加样例

见 下发 的 years/years2.in 和 years/years2.ans 至 years/years10.in 和 years/years10.ans。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（1 pts）：$n = 1$。
• Subtask 2（1 pts）：$n = 2$。
• Subtask 3（1 pts）：$n = 3$。
• Subtask 4（1 pts）：$n = 4$。
• Subtask 5（1 pts）：$n = 5$。
• Subtask 6（1 pts）：$n = 6$。
• Subtask 7（1 pts）：$n = 7$。
• Subtask 8（1 pts）：$n = 8$。
• Subtask 9（1 pts）：$n = 9$。
• Subtask 10（1 pts）：$n = 10$。
• Subtask 11（3 pts）：$n = 11$。
• Subtask 12（9 pts）：$n = 12$。
• Subtask 13（12 pts）：$n = 13$。
• Subtask 14（13 pts）：$n = 14$。
• Subtask 15（13 pts）：$n = 15$。
• Subtask 16（20 pts）：$n = 16$。
• Subtask 17（20 pts）：$n = 17$。

对于所有数据，保证 $1 \leq n \leq 17$，$0 \leq m \leq \frac{n(n-1)}{2}$，$1 \leq u_i, v_i \leq n$，图无重边、自环。