406116: GYM102268 I Interesting Graph

Memory Limit:0 MB Time Limit:5 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Interesting Graphtime limit per test5 secondsmemory limit per test256 mebibytesinputstandard inputoutputstandard output

You have an undirected graph with the following property:

For any subset $$$A$$$ of $$$7$$$ vertices of the graph, there are some two vertices $$$a, b \in A$$$ and some vertex $$$c \notin A$$$ such that all paths from $$$a$$$ to $$$b$$$ contain vertex $$$c$$$.

You need to find the number of ways to properly color this graph in $$$1, 2, \ldots, n$$$ colors modulo $$$998\,244\,353$$$.

A graph is colored in $$$k$$$ colors by assigning an integer color from $$$1$$$ to $$$k$$$ to every vertex. A coloring is proper if the endpoints of each edge in the graph have different colors.

Input

The first line of the input contains two integers $$$n$$$ and $$$m$$$: the number of vertices and the number of edges in your graph ($$$1 \leq n, m \leq 10^5$$$).

The next $$$m$$$ lines contain description of the edges of the graph. Each of these lines contains two integers $$$a_i$$$ and $$$b_i$$$ describing an edge between vertices $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$). There are no multiple edges.

It is guaranteed that for any subset $$$A$$$ of $$$7$$$ vertices of the graph, there are some two vertices $$$a, b \in A$$$ and some vertex $$$c \notin A$$$ such that all paths from $$$a$$$ to $$$b$$$ contain vertex $$$c$$$.

Output

Print one line containing $$$n$$$ space-separated integers. The $$$i$$$-th integer must be the number of ways to properly color this graph in $$$i$$$ colors, taken modulo $$$998\,244\,353$$$.

ExampleInput
5 3
3 5
5 1
1 3
Output
0 0 54 384 1500 

Source/Category

加入题单

上一题 下一题 算法标签: