简单环
题号:NC16544
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给定一张n个点m条边的无向图,求出图中所有简单环的数量。(简单环:简单环又称简单回路,图的顶点序列中,除了第一个顶点和最后一个顶点相同外,其余顶点不重复出现的回路叫简单回路。或者说,若通路或回路不重复地包含相同的边,则它是简单的)

输入描述:

第一行三个数n m k (k在输出描述中提到)
接下来m行每行两个数u,v表示u到v之间存在一条边(无重边)

输出描述:

输出k行每行1个整数
第i个数表示长度%k==i-1的简单环的数量(对998244353取模)
(只记录长度大于2的简单环的数量)
示例1

输入

复制
4 6 3
1 2
2 3
3 4
4 1
2 4
1 3

输出

复制
4
3
0

备注:

n<=20
m<=n*(n-1)/2
k<=n