Safety Journey

题目描述

阿托德卡共和国有 $N$ 个城市，分别称为 城市 1、城市 2、…、城市 $N$。 起初，每一对不同城市之间都有一条双向道路，但其中有 $M$ 条道路因年久失修而无法使用。更具体地，对于每个 $1\leq i \leq M$，连接 城市 $U_i$ 和 城市 $V_i$ 的道路已不能使用。 高桥将进行一个从 城市 1 出发并在 城市 1 结束的为期 $K$ 天的旅行。形式上，起止于 城市 1 的 $K$ 天旅行是一个由 $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}$。 输出从 城市 1 出发并在 城市 1 结束的不同 $K$ 天旅行的数量，对 $998244353$ 取模。这里，当存在某个 $i$ 使得 $A_i\neq B_i$ 时，我们说两个 $K$ 天旅行 $(A_0, A_1, \ldots, A_K)$ 与 $(B_0, B_1, \ldots, B_K)$ 不同。

输入格式

输入以标准输入给出，格式如下： $N$ $M$ $K$ $U_1$ $V_1$ : $U_M$ $V_M$

输出格式

输出答案。

3 1 4
2 3

4

3 3 3
1 2
1 3
2 3

0

5 3 100
1 2
4 5
2 3

428417047

提示

$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,2,1,2,1$) ($1,2,1,3,1$) ($1,3,1,2,1$) ($1,3,1,3,1$)

没有其他有效的旅行，所以我们应当输出 $4$。
没有道路可用，所以不存在有效的旅行。

标签: AtCoder|abc212E

来源

AtCoder|abc212E