18455번 - Interesting Graph 다국어

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 ∈ A and some vertex c ∉ 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, . . . , 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.

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 ≤ n, m ≤ 10⁵).

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 ≤ a_i, b_i ≤ n, a_i ̸= 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 ∈ A and some vertex c ∉ A such that all paths from a to b contain vertex c.

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.