1012. 数一数环的个数

题目描述

给定一个包含 $n$ 个点和 $m$ 条边的无向图，点编号为 $1,2,\ldots,n$。

图中可能存在连接同一对点的多条边，每条输入的边均视为一条不同的边。

保证存在一种将所有点染成黑色或白色的方案，使每条边的两个端点颜色不同。

一个环是一个连通子图，并且该子图中每个点的度数均为 $2$。如果一个环恰好包含 $k$ 个点，则称其为一个 $k$ 元环。

求图中不同 $k$ 元环的数量。两个环不同，当且仅当它们选择的边集不同。

答案可能很大，请对 $998244353$ 取模。

输入格式

第一行输入一个整数 $T$，表示测试数据组数。

每组测试数据的格式如下：

第一行输入三个整数 $n,m,k$，分别表示点数、边数和需要统计的环的点数。输入保证 $k$ 是质数。

接下来 $m$ 行，每行输入两个整数 $u,v$，表示一条连接点 $u$ 和点 $v$ 的无向边。

相同的 $(u,v)$ 可能出现多次，每次出现均表示一条不同的边。

对于一组测试数据：

$2\le n\le 2\times 10^5$；

$0\le m\le 10^6$；

$2\le k\le n$；

$1\le u,v\le n$；

输入保证存在一种黑白染色方案，使每条边的两个端点颜色不同。

OJ 中只有一个正式测试点，该测试点满足：

$T=10000$；

$\sum n=10^6$；

$\sum m=2\times 10^6$。

输出格式

对于每组测试数据输出一行，表示图中不同 $k$ 元环的数量，对 $998244353$ 取模后的结果。

样例输入

3
2 3 2
1 2
1 2
1 2
4 4 3
1 2
2 3
3 4
4 1
3 2 2
1 2
2 3

样例输出

3
0
0

来源：2026杭电多校-测试专用（肖岱恩） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1236&pid=1012