#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

char buf[1 << 23], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1 ++)
int read() {
	int s = 0, w = 1; char ch = getchar();
	while(!isdigit(ch)) { if(ch == '-') w = -1; ch = getchar(); }
	while(isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return s * w;
}

int dis[2][N], deg[N];
vector<int> G[N];
bool leaf[N];
int T, n, m, s, t, cas;

queue<int> q;
void bfs(int *d, int s) {
	q.push(s), d[s] = 0;
	while(q.size()) {
		int u = q.front(); q.pop();
		for(auto v : G[u]) if(d[v] == -1)
			d[v] = d[u] + 1, q.push(v);
	}
}
void mark() {
	for(int i = 1; i <= n; ++ i)
		if(deg[i] == 1) q.push(i);
	while(q.size()) {
		int u = q.front(); q.pop(), leaf[u] = true;
		for(auto v : G[u]) if(-- deg[v] == 1) q.push(v);
	}
}

signed main() {
	T = read();
	while(T --) {
		n = read(), m = read(), s = read(), t = read();
		for(int i = 1; i <= n; ++ i)
			dis[0][i] = dis[1][i] = -1, 
			deg[i] = leaf[i] = 0,
			G[i].clear();
		for(int i = 1, u, v; i <= m; ++ i)
			u = read(), v = read(), 
			G[u].push_back(v), G[v].push_back(u),
			++ deg[u], ++ deg[v];
		
		bfs(dis[0], s), bfs(dis[1], t), mark();
			
		printf("Case #%d: ", ++ cas);
		if(dis[0][t] == -1) { puts("SAFE"); continue; }
		int ans = -1;
		for(int i = 1; i <= n; ++ i) if(dis[0][i] < dis[1][i]) {
			if(leaf[i]) ans = max(ans, dis[1][i]);
			else { puts("SAFE"), ans = -1; break; }
		}
		if(ans != -1) printf("%d\n", ans * 2);
	}
	return 0;
}