CF1662C.European Trip

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$.

欧洲地图可以表示为由 $n$ 个城市（编号从 $1$ 到 $n$）组成的集合，这些城市之间由 $m$ 条双向道路连接，每条道路连接两个不同的城市。长度为 $k$ 的行程是指一个包含 $k+1$ 个城市的序列 $v_1, v_2, \ldots, v_{k+1}$，使得对每个 $1 \le i \le k$，城市 $v_i$ 与 $v_{i+1}$ 之间均存在一条道路。特殊行程是指不连续两次经过同一条道路的行程，即一个包含 $k+1$ 个城市的序列 $v_1, v_2, \ldots, v_{k+1}$，它本身是一个行程，且对所有 $1 \le i \le k - 1$ 满足 $v_i \neq v_{i + 2}$。

给定整数 $k$，计算所有起点与终点为同一城市的、长度为 $k$ 的不同特殊行程的数量。由于答案可能很大，请将结果对 $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).

第一行包含三个整数 $n$、$m$ 和 $k$（$3 \le n \le 100$，$1 \le m \le n(n - 1) / 2$，$1 \le k \le 10^4$），分别表示城市的数量、道路的数量以及需要考虑的旅行长度。

接下来的 $m$ 行中，每行包含一对互异的整数 $a$ 和 $b$（$1 \le a, b \le n$），每对数表示一条连接城市 $a$ 和 $b$ 的道路。保证所有道路互不相同（即任意两个城市之间至多只有一条道路相连）。

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

输出长度为 $k$ 且起点与终点为同一城市的特殊行程的数量，结果对 $998\,244\,353$ 取模。

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)$.

在第一个样例中，我们需要寻找长度为 $2$ 的特殊路径，但由于不能重复使用同一条道路，因此一旦离开某个城市就无法返回，故答案为 $0$。

在第二个样例中，存在以下 $12$ 条长度为 $3$ 且起点与终点为同一城市的特殊路径：$(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)$ 和 $(4, 2, 1, 4)$。