很容易看出来这是个 $dp$ ，只不过因为限制需要多几维而已。差不多是 $dp[u][j][c]$ 表示 $u$ 号点第 $j$ 步整数 $x$ 出现次数除以 $2$ 的余数是 $c$ 时序列的个数。

不过，搜索还是很好写的，加个记忆化即可。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int T = 1;
const int N = 2000 + 10;
const int MOD = 998244353;

int n, m, k, s, t, x, ans;
vector<vector<int>> graph(N);

int dp[N][N][2];//dp[u][k][x(0/1)]

int Dfs(int u, int p, int c) {
	if (dp[u][p][c % 2] != -1) {
		return dp[u][p][c % 2];
	}
	if (p == k) {
		if (u == t && c % 2 == 0) {
			return 1;
		}
		return 0;
	}
	int res = 0;
	for (auto v : graph[u]) {
		if (v == x) c++;
		res = (res + Dfs(v, p + 1, c)) % MOD;
		if (v == x) c--;
	}
	dp[u][p][c % 2] = res;
	return res;
}

void Solve() {
	cin >> n >> m >> k >> s >> t >> x;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	memset(dp, -1, sizeof(dp));
	cout << Dfs(s, 0, (s == x));
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	while (T--) {
		Solve();
	}
	return 0;
}