/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
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 となることを言います。
制約
- 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) は全て互いに相異なる。
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M K U_1 V_1 : U_M V_M
出力
答えを出力せよ。
入力例 1
3 1 4 2 3
出力例 1
4
次のような 4 種類の旅が存在します。
- (1,2,1,2,1)
- (1,2,1,3,1)
- (1,3,1,2,1)
- (1,3,1,3,1)
これ以外に条件をみたすようなものは無いため、 4 を出力します。
入力例 2
3 3 3 1 2 1 3 2 3
出力例 2
0
使える道が 1 本も残っておらず、条件をみたすような旅は存在しません。
入力例 3
5 3 100 1 2 4 5 2 3
出力例 3
428417047
Score : 500 points
Problem Statement
The Republic of AtCoder has N cities, called City 1, City 2, \ldots, City N. Initially, there was a bidirectional road between every pair of different cities, but M of these roads have become unusable due to deterioration over time. More specifically, for each 1\leq i \leq M, the road connecting City U_i and City V_i has become unusable.
Takahashi will go for a K-day trip that starts and ends in City 1. Formally speaking, a K-day trip that starts and ends in City 1 is a sequence of K+1 cities (A_0, A_1, \ldots, A_K) such that A_0=A_K=1 holds and for each 0\leq i\leq K-1, A_i and A_{i+1} are different and there is still a usable road connecting City A_i and City A_{i+1}.
Print the number of different K-day trips that start and end in City 1, modulo 998244353. Here, two K-day trips (A_0, A_1, \ldots, A_K) and (B_0, B_1, \ldots, B_K) are said to be different when there exists an i such that A_i\neq B_i.
Constraints
- 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
- All pairs (U_i, V_i) are pairwise distinct.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M K U_1 V_1 : U_M V_M
Output
Print the answer.
Sample Input 1
3 1 4 2 3
Sample Output 1
4
There are four different trips as follows.
- (1,2,1,2,1)
- (1,2,1,3,1)
- (1,3,1,2,1)
- (1,3,1,3,1)
No other trip is valid, so we should print 4.
Sample Input 2
3 3 3 1 2 1 3 2 3
Sample Output 2
0
No road remains usable, so there is no valid trip.
Sample Input 3
5 3 100 1 2 4 5 2 3
Sample Output 3
428417047