AT_abc212_e [ABC212E] Safety Journey

[problemUrl]: https://atcoder.jp/contests/abc212/tasks/abc212_e 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 $

答えを出力せよ。

### 制約 - $ 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\