#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, A, Q;
vector<int> g[100010]; int ind[100010], bk[100010], disA[100010], disQ[100010]; map<int, bool> p[100010];
void bfs(int s, int *dis) {
	queue<int> q; q.push(s); dis[s] = 0;
	while (q.size()) {
		int u = q.front(); q.pop();
		for (int i = 0; i < g[u].size(); i++) {
			int v = g[u][i];
			if (dis[v] >= 1e18) {
				dis[v] = dis[u] + 1; q.push(v);
			}
		}
	}
}
queue<int> q; 
signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	for (int _ = 1; _ <= T; _++) {
		cin >> n >> m >> A >> Q;
		memset(ind, 0, sizeof ind);
		for (int i = 1; i <= n; i++) g[i].clear(), p[i].clear();
		for (int i = 1; i <= m; i++) {
			int u, v;
			cin >> u >> v;
			if (p[u][v]) continue; 
			p[u][v] = 1; p[v][u] = 1;
			g[u].push_back(v), g[v].push_back(u); ind[u]++, ind[v]++;
		}
		for (int i = 1; i <= n; i++)
			if (ind[i] == 1) {
				q.push(i);
			}
		memset(bk, 0, sizeof bk);
		while (q.size()) {
			int u = q.front(); q.pop(); bk[u] = 1;
			for (int i = 0; i < g[u].size(); i++) {
				int v = g[u][i];
				ind[v]--;
				if (ind[v] == 1) q.push(v);
			}
		}
		fill(disA + 1, disA + n + 1, 1e18);
		fill(disQ + 1, disQ + n + 1, 1e18);
		bfs(A, disA); bfs(Q, disQ);
		int ans = 0;
		for (int i = 1; i <= n; i++)
			if ((disA[i] < disQ[i] && disQ[i] == 1e18) || (!bk[i] && disA[i] < disQ[i])) {
				ans = 1e18;
			} else if (disA[i] < disQ[i]) ans = max(ans, disQ[i]);
		cout << "Case #" << _ << ": " << (ans > 2 * n ? "SAFE" : to_string(ans * 2)) << "\n";
	}
	return 0;
}