1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| #include <iostream>
#include <queue>
#define maxn 1010
#define maxm 200010
#define INF 1000000000
using namespace std;
int n, m, s0, s1, t;
vector<int> G[maxn];
struct Edge {
int to, next;
} e[maxm * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}
int dis[maxn]; bool vis[maxn];
void bfs(int s) {
queue<int> Q; Q.push(s);
fill(dis + 1, dis + n + 1, INF); dis[s] = 0;
fill(vis + 1, vis + n + 1, 0); vis[s] = 0;
while (!Q.empty()) {
int u = Q.front(); Q.pop();
for (auto v : G[u]) {
if (vis[v]) {
if (dis[v] == dis[u] + 1) add_edge(v, u);
continue;
} vis[v] = 1; add_edge(v, u);
dis[v] = dis[u] + 1; Q.push(v);
}
}
}
int f[maxn][maxn][2];
int dp(int x, int y, int z, int o) {
if (f[x][y][o] != -2) return f[x][y][o];
if (!o && (x == z || y == z)) {
if (x == z && y == z) return 0;
if (x == z) return 1;
return -1;
}
int u = x, v = y; if (o) swap(u, v); bool win = 0, draw = 0;
for (int i = head[u]; ~i; i = e[i].next) {
int t = e[i].to; if (t == v && t != z) continue;
int g = !o ? dp(t, y, z, o ^ 1) : dp(x, t, z, o ^ 1);
if (!g) draw = 1;
else if (g < 0) win = 1;
}
if (win) f[x][y][o] = 1;
else if (draw) f[x][y][o] = 0;
else f[x][y][o] = -1;
return f[x][y][o];
}
void work() {
cin >> n >> m >> s0 >> s1 >> t;
fill(head + 1, head + n + 1, -1); c1 = 0;
for (int i = 1; i <= n; ++i) G[i].clear();
for (int i = 1; i <= m; ++i) {
int x, y; cin >> x >> y;
G[x].push_back(y); G[y].push_back(x);
} bfs(t);
if (dis[s0] < dis[s1]) return cout << 1 << "\n", void();
if (dis[s1] < dis[s0]) return cout << 3 << "\n", void();
if (dis[s0] == INF) return cout << 2 << "\n", void();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) f[i][j][0] = f[i][j][1] = -2;
int ans = dp(s0, s1, t, 0);
if (ans == -1) cout << 3 << "\n";
else if (ans == 0) cout << 2 << "\n";
else cout << 1 << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) work();
return 0;
}
|