#include <bits/stdc++.h>
using namespace std;
const int sizen = 100003, sizem = 200003;
struct Edge {
	int v, nxt;
} edge[sizem * 2];
int head[sizen], cnt;
int disa[sizen], disb[sizen];
int in[sizen];
void add_edge(int u, int v) {
	edge[++cnt] = (Edge){v, head[u]};
	head[u] = cnt;
	++in[v];
}
int n, m, A, B;
void topu() {
	queue<int> q;
	for (int i = 1; i <= n; ++i) if (in[i] == 1) q.push(i);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int i = head[u]; ~i; i = edge[i].nxt) {
			int v = edge[i].v;
			--in[v];
			if (in[v] == 1) q.push(v);
		}
	}
}
int main() { 
	ios::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T; for (int nb = 1; nb <= T; ++nb) {
		cin >> n >> m >> A >> B;
		memset(head, -1, sizeof(head)); cnt = 0;
		memset(disa, 0, sizeof(disa));
		memset(disb, 0, sizeof(disb));
		memset(in, 0, sizeof(in));
		for (int i = 1; i <= m; ++i) {
			int u, v; cin >> u >> v;
			add_edge(u, v); add_edge(v, u);
		}
		queue<int> q; q.push(A);
		disa[A] = 1;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (int i = head[u]; ~i; i = edge[i].nxt) {
				int v = edge[i].v;
				if (disa[v]) continue;
				disa[v] = disa[u] + 1;
				q.push(v);
			}
		}
		q.push(B);
		disb[B] = 1;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (int i = head[u]; ~i; i = edge[i].nxt) {
				int v = edge[i].v;
				if (disb[v]) continue;
				disb[v] = disb[u] + 1;
				q.push(v);
			}
		}
		topu();
		bool flag = true;
		int maxn = 0;
//		cout << "@" << A << " " << B << endl;
		for (int i = 1; i <= n && flag; ++i) {
//			cout << i << " " << disa[i] << " " << disb[i] << endl;
			if (in[i] > 1) {
				if (disa[i] < disb[i]) {
					flag = false;
				}
			} else if (disa[i] < disb[i]) maxn = max(maxn, disb[i] - 1);
		}
		cout << "Case #" << nb << ": ";
		if (flag && disa[B] != 0) cout << maxn * 2 << endl;
		else cout << "SAFE" << endl;
	}
	return 0; 
}