安全旅程

题目描述

AtCoder 共和国有 $N$ 座城市,称为城市 $1$,城市 $2$,$\ldots$,城市 $N$。最初,任意两座不同城市之间都有一条双向道路,但由于年久失修,其中 $M$ 条道路已经无法使用。具体来说,对于每个 $1\le i\le M$,连接城市 $U_i$ 和城市 $V_i$ 的道路已经无法使用。

高桥君将进行一个从城市 $1$ 出发并在城市 $1$ 结束的 $K$ 天旅行。形式上,从城市 $1$ 出发并在城市 $1$ 结束的 $K$ 天旅行是一个由 $K+1$ 座城市组成的序列 $(A_0,A_1,\ldots,A_K)$,满足 $A_0=A_K=1$,并且对于每个 $0\le i\le K-1$,$A_i$ 与 $A_{i+1}$ 不同,且城市 $A_i$ 和城市 $A_{i+1}$ 之间仍有可用的道路。

求从城市 $1$ 出发并回到城市 $1$ 的不同 $K$ 天旅行方案数,对 $998244353$ 取模。这里,两个 $K$ 天旅行 $(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$
$:$
$U_M$ $V_M$

输出格式

输出答案。

样例

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

数据范围

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