题目描述

AtCoder国には $N$ 個の都市があり、都市 $1$ , 都市 $2$ , $\ldots$ , 都市 $N$ と番号付けられています。 最初、どの $2$ つの相異なる都市の間も双方向に通れる道で結ばれていましたが、老朽化が進み、これらのうち $M$ 本の道が使えなくなってしまいました。具体的には $1\leq\ i\ \leq\ 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\leq\ i\leq\ K-1$ について $A_i$ と $A_{i+1}$ が相異なり、かつ都市 $A_i$ と都市 $A_{i+1}$ が現在も使用可能な道で結ばれているものを指します。

都市 $1$ で始まり、都市 $1$ で終わる $K$ 日間の相異なる旅の数を $998244353$ で割った余りを出力してください。ただし、 $2$ つの $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$

输出格式

答えを出力せよ。

题目大意

给定一个完全图，并在其中去除 $m$ 条边。求有多少条路线，满足从 $1$ 号点出发，走了 $k$ 步路之后回到 $1$ 号点。

translated by

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)$ は全て互いに相異なる。
• 入力は全て整数である。

Sample Explanation 1

次のような $4$ 種類の旅が存在します。 - ($1,2,1,2,1$) - ($1,2,1,3,1$) - ($1,3,1,2,1$) - ($1,3,1,3,1$) これ以外に条件をみたすようなものは無いため、 $4$ を出力します。

Sample Explanation 2

使える道が $1$ 本も残っておらず、条件をみたすような旅は存在しません。