CF1662C European Trip

欧洲的地图可以表示为 $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}$ 之间都有道路相连。特殊旅行是指在旅行过程中不能连续两次经过同一条道路，即对于所有 $1 \le i \le k-1$，有 $v_i \neq v_{i+2}$。 给定整数 $k$，计算长度为 $k$ 且起点和终点为同一城市的不同特殊旅行的数量。由于答案可能很大，请输出对 $998\,244\,353$ 取模的结果。

第一行包含三个整数 $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$ 之间有一条道路。保证每对城市之间至多只有一条道路。

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

在第一个样例中，我们要求长度为 $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)$。 由 ChatGPT 4.1 翻译