European Trip

题意翻译

给定一张 $n$ 个点， $m$ 条边的无向图，（边的长度为$1$）求有多少条长度为 $k$ 的路径，满足 - 起点和终点相同 - 不存在相邻两步走同一条边，即不存在 $a \to b \to a$ 的路径 答案对$998244353$取模 数据范围：$3 \le n \le 100, \ 1 \le m \le \frac{n(n - 1)}{2}, \ 1 \le k \le 10^4$

题目描述

The map of Europe can be represented by a set of $ n $ cities, numbered from $ 1 $ through $ n $ , which are connected by $ m $ bidirectional roads, each of which connects two distinct cities. A trip of length $ k $ is a sequence of $ k+1 $ cities $ v_1, v_2, \ldots, v_{k+1} $ such that there is a road connecting each consecutive pair $ v_i $ , $ v_{i+1} $ of cities, for all $ 1 \le i \le k $ . A special trip is a trip that does not use the same road twice in a row, i.e., a sequence of $ k+1 $ cities $ v_1, v_2, \ldots, v_{k+1} $ such that it forms a trip and $ v_i \neq v_{i + 2} $ , for all $ 1 \le i \le k - 1 $ . Given an integer $ k $ , compute the number of distinct special trips of length $ k $ which begin and end in the same city. Since the answer might be large, give the answer modulo $ 998\,244\,353 $ .

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ and $ k $ ( $ 3 \le n \le 100 $ , $ 1 \le m \le n(n - 1) / 2 $ , $ 1 \le k \le 10^4 $ ) — the number of cities, the number of roads and the length of trips to consider. Each of the following $ m $ lines contains a pair of distinct integers $ a $ and $ b $ ( $ 1 \le a, b \le n $ ) — each pair represents a road connecting cities $ a $ and $ b $ . It is guaranteed that the roads are distinct (i.e., each pair of cities is connected by at most one road).

输出格式

Print the number of special trips of length $ k $ which begin and end in the same city, modulo $ 998\,244\,353 $ .

输入输出样例

输入样例 #1

4 5 2
4 1
2 3
3 1
4 3
2 4

输出样例 #1

0

输入样例 #2

4 5 3
1 3
4 2
4 1
2 1
3 4

输出样例 #2

12

输入样例 #3

8 20 12
4 3
6 7
5 7
8 2
8 3
3 1
4 7
8 5
5 4
3 5
7 1
5 1
7 8
3 2
4 2
5 2
1 4
4 8
3 6
4 6

输出样例 #3

35551130

说明

In the first sample, we are looking for special trips of length $ 2 $ , but since we cannot use the same road twice once we step away from a city we cannot go back, so the answer is $ 0 $ . In the second sample, we have the following $ 12 $ special trips of length $ 3 $ which begin and end in the same city: $ (1, 2, 4, 1) $ , $ (1, 3, 4, 1) $ , $ (1, 4, 2, 1) $ , $ (1, 4, 3, 1) $ , $ (2, 1, 4, 2) $ , $ (2, 4, 1, 2) $ , $ (3, 1, 4, 3) $ , $ (3, 4, 1, 3) $ , $ (4, 1, 3, 4) $ , $ (4, 3, 1, 4) $ , $ (4, 1, 2, 4) $ , and $ (4, 2, 1, 4) $ .