#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int N = 1e5 + 10;
int T, n, m, s, t;
vector <int> G[N];
int in[N], dis[2][N];

inline void bfs(int s, int *dis){
	queue <int> q;
	q.push(s), dis[s] = 0;
	while(!q.empty()){
		int x = q.front(); q.pop();
		for(auto y : G[x])
			if(dis[y] > dis[x] + 1)
				dis[y] = dis[x] + 1, q.push(y);
	}
}

inline void solve(int Case){
	cin >> n >> m >> s >> t;
	for(int i = 0; i <= n + 5; ++i){
		in[i] = 0, dis[0][i] = dis[1][i] = 1e9;
		G[i].clear(), G[i].clear();
	}
	for(int i = 1; i <= m; ++i){
		int u, v; cin >> u >> v;
		G[u].pb(v), G[v].pb(u), in[u]++, in[v]++;
	}
	bfs(s, dis[0]), bfs(t, dis[1]); 
	
	cout << "Case #" << Case << ": ";
	if(dis[0][t] == 1e9) return cout << "SAFE\n", void();
	queue <int> q;
	for(int i = 1; i <= n; ++i)
		if(in[i] <= 1) q.push(i);
	while(!q.empty()){
		int x = q.front(); q.pop();
		for(auto y : G[x])
			if((--in[y]) == 1) q.push(y);
	}
//	cout << "???" << endl;
	for(int i = 1; i <= n; ++i)
		if(in[i] > 1 && dis[1][i] < 1e9 && dis[0][i] < dis[1][i]) return cout << "SAFE\n", void();
	int mx = 0;
	for(int i = 1; i <= n; ++i)
		if(dis[0][i] < dis[1][i]) mx = max(mx, dis[1][i]);
	cout << (mx << 1) << '\n';
}

signed main(){
	ios :: sync_with_stdio(false);
	cin >> T;
	for(int i = 1; i <= T; ++i) solve(i);
	return 0;
}