시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 11 | 8 | 8 | 72.727% |
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 ≤ 105).
The next m lines contain description of the edges of the graph. Each of these lines contains two integers ai and bi describing an edge between vertices ai and bi (1 ≤ ai, bi ≤ n, ai ̸= bi). 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.
5 3 3 5 5 1 1 3
0 0 54 384 1500
Camp > Petrozavodsk Programming Camp > Winter 2019 > Day 1: 300iq Contest I번