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 翻译