408766: GYM103306 A Alice Birthday
Description
Recently Alice celebrated her birthday. Bob knows that collecting graphs is a hobby for Alice, for that reason he decided to give her an undirected graph for her birthday. The graph consisted of $$$N$$$ nodes and $$$M$$$ undirected edges.
Alice was playing with her new graph when she started wondering what would happen if she deleted some edges from the graph. She thinks that the number of connected components is an important property for graphs, so she would like to know how many ways of deleting some edges there are so the graph have $$$K$$$ connected components after deleting such edges.
For all $$$K$$$ from $$$1$$$ to $$$N$$$, help Alice to find the number of ways of deleting e dges so the graph has $$$K$$$ connected components. Two ways of deleting edges are different if there is an edge that is deleted in a way but not in the other. It is allowed to delete all edges or not to delete any edge at all.
InputThe first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 14$$$ and $$$0 \leq M \leq \frac{N(N-1)}{2}$$$), the number of nodes and the number of edges.
Each of the following $$$M$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u,v \leq N$$$ and $$$u \neq v$$$), the nodes that the edges connect. It is guaranteed that there are not multiple edges connecting a single pair of nodes.
OutputPrint $$$N$$$ lines. In the $$$K$$$-th line print the number of ways of deleting some edges so there are $$$K$$$ connected components after deleting such edges. Print the answer modulo $$$998244353$$$.
ExamplesInput5 4 1 2 1 3 1 4 1 5Output
1 4 6 4 1Input
2 0Output
0 1Input
4 6 1 2 1 3 1 4 2 3 2 4 3 4Output
38 19 6 1