AT_abc212_e.[ABC212E] Safety Journey

AtCoder 国有 $N$ 个城市，编号为 $1$、$2$、$\ldots$、$N$。最初，任意两个不同的城市之间都有一条可以双向通行的道路相连，但由于年久失修，其中有 $M$ 条道路无法再使用。具体来说，对于 $1 \leq i \leq M$，连接城市 $U_i$ 和城市 $V_i$ 的道路无法再使用。

现在，高桥君打算进行一次为期 $K$ 天的旅行，从城市 $1$ 出发，最终回到城市 $1$。所谓为期 $K$ 天、从城市 $1$ 出发并回到城市 $1$ 的旅行，是指存在一个长度为 $K+1$ 的城市序列 $(A_0, A_1, \ldots, A_K)$，满足 $A_0 = A_K = 1$，对于 $0 \leq i \leq K-1$，$A_i$ 与 $A_{i+1}$ 不相同，且城市 $A_i$ 与城市 $A_{i+1}$ 之间有一条当前仍可使用的道路直接相连。

请输出满足条件的不同旅行方案数对 $998244353$ 取模的结果。若存在两个旅行 $(A_0, A_1, \ldots, A_K)$ 和 $(B_0, B_1, \ldots, B_K)$，使得存在某个 $i$ 满足 $A_i \neq B_i$，则认为这两个旅行是不同的。

输入以如下格式从标准输入读入。

$N$ $M$ $K$
$U_1$ $V_1$
$\vdots$
$U_M$ $V_M$

输出答案。

限制条件

• $2 \leq N \leq 5000$
• $0 \leq M \leq \min\left(\frac{N(N-1)}{2}, 5000\right)$
• $2 \leq K \leq 5000$
• $1 \leq U_i < V_i \leq N$
• 所有 $(U_i, V_i)$ 互不相同。
• 所有输入均为整数。

样例解释 1

存在如下 $4$ 种旅行方案：

• $(1,2,1,2,1)$
• $(1,2,1,3,1)$
• $(1,3,1,2,1)$
• $(1,3,1,3,1)$

除此之外，没有其他满足条件的方案，因此输出 $4$。

样例解释 2

没有任何可用的道路，因此不存在满足条件的旅行方案。

由 ChatGPT 4.1 翻译