Score : $600$ points

问题描述

给定一个包含 $N$ 个顶点和 $M$ 条边的简单无向图 $G$。顶点编号为 $1,2,\dots,N$，边编号为 $1,2,\dots,M$，其中第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。

考虑从 $G$ 中移除零个或多个边以得到一个新的图 $H$。我们可以得到 $2^M$ 种不同的图作为 $H$。在这些图中，对于每个满足 $2 \leq k \leq N$ 的整数 $k$，找出顶点 $1$ 和顶点 $k$ 直接或间接相连的图的数量。

由于数量可能非常大，将结果对 $998244353$ 取模后输出。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Given is a simple undirected graph $G$ with $N$ vertices and $M$ edges. The vertices are numbered $1,2,\dots,N$, the edges are numbered $1,2,\dots,M$, and Edge $i$ connects Vertex $a_i$ and Vertex $b_i$.
Consider removing zero or more edges from $G$ to get a new graph $H$. There are $2^M$ graphs that we can get as $H$. Among them, find the number of such graphs that Vertex $1$ and Vertex $k$ are directly or indirectly connected, for each integer $k$ such that $2 \leq k \leq N$.
Since the counts may be enormous, print them modulo $998244353$.

Constraints

• $2 \leq N \leq 17$
• $0 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq a_i \lt b_i \leq N$
• $(a_i, b_i) \neq (a_j, b_j)$ if $i \neq j$.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$

$a_1$ $b_1$

$\vdots$

$a_M$ $b_M$

Output

Print $N-1$ lines. The $i$-th line should contain the answer for $k = i + 1$.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

2
1

We can get the following graphs as $H$.

• The graph with no edges. Vertex $1$ is disconnected from any other vertex.
• The graph with only the edge connecting Vertex $1$ and $2$. Vertex $2$ is reachable from Vertex $1$.
• The graph with only the edge connecting Vertex $2$ and $3$. Vertex $1$ is disconnected from any other vertex.
• The graph with both edges. Vertex $2$ and $3$ are reachable from Vertex $1$.

Sample Input 2

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

Sample Output 2

43
31
37
41

Sample Input 3

2 0

Sample Output 3

0

update @ 2024/3/10 09:30:20