E - Safety Journey
E - 安全之旅
分数：$500$ 分
问题描述
Atcoder 共有 $N$ 个城市，分别被称为 City $1$，City $2$，$\ldots$，City $N$。 最初，每对不同的城市之间都有一条双向道路，但其中 $M$ 条由于时间推移而不可用。具体来说，对于每个 $1\leq i \leq M$，连接 City $U_i$ 和 City $V_i$ 的道路已变得不可用。
Takahashi 将进行一次 $K$ 天的旅行，旅行开始和结束于 City $1$。严格来说，以 City $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}$ 是不同的，并且 City $A_i$ 和 City $A_{i+1}$ 之间仍有可用道路。
输出以 City $1$ 为起点和终点的不同 $K$ 天旅行的数量，模 $998244353$。在这里，当存在一个 $i$ 使得 $A_i\neq B_i$ 时，两个 $K$ 天旅行 $(A_0, A_1, \ldots, A_K)$ 和 $(B_0, B_1, \ldots, B_K)$ 被称为不同的旅行。
约束条件
- $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)$ 都是两两不同的。
- 输入中的所有值都是整数。
输入
从标准输入读入数据，格式如下：
输出
打印答案。
3 1 4
2 3
4
有四种不同的旅行，如下所示。
- ($1,2,1,2,1$)
- ($1,2,1,3,1$)
- ($1,3,1,2,1$)
- ($1,3,1,3,1$)
没有其他有效的旅行，所以我们应该输出 $4$。
3 3 3
1 2
1 3
2 3
0
没有道路可用，所以没有有效的旅行。
5 3 100
1 2
4 5
2 3
428417047