#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef pair<int,int> PII;
int n,m,A,B,ind[N],usafe[N],dis[2][N],vis[N];	
vector<int> g[N];
void dij(int op,int st) {
	memset(vis,0,sizeof(vis));
	priority_queue<PII,vector<PII>,greater<PII>> q;
	dis[op][st]=0; q.emplace(0,st);
	while(q.size()) {
		int u=q.top().second; q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(auto to:g[u]) if(dis[op][to]>dis[op][u]+1){
			dis[op][to]=dis[op][u]+1; q.emplace(dis[op][to],to);
		}
	}
}
bool dfs(int x) {
	vis[x]=1;
	for(auto to:g[x]) if(!vis[to]) dfs(to);
}
int test;
void solve() {
	scanf("%d%d%d%d",&n,&m,&A,&B);
	for(int i=1;i<=n;i++) g[i].clear();
	memset(ind,0,sizeof(ind)), memset(usafe,0,sizeof(usafe)), memset(dis,0x3f,sizeof(dis));
	for(int i=1,u,v;i<=m;i++) {
		scanf("%d%d",&u,&v);
		g[u].emplace_back(v), g[v].emplace_back(u);
		ind[u]++, ind[v]++;
	}
	queue<int> q;
	for(int i=1;i<=n;i++) if(ind[i]<=1) q.emplace(i);
	while(q.size()) {
		int u=q.front(); q.pop();
		usafe[u]=1;
		for(auto to:g[u]) if(!usafe[to]) {
			ind[to]--;
			if(ind[to]<=1) q.emplace(to);
		}
	}
	memset(vis,0,sizeof(vis)); dfs(A);
	if(!vis[B]) return printf("Case #%d: SAFE\n",++test), void();
	dij(0,A), dij(1,B);
	int ans=0;
	for(int i=1;i<=n;i++) {
		if(dis[0][i]<dis[1][i]) {
			if(!usafe[i]) ans=INT_MAX;
			else ans=max(ans,dis[1][i]);
		}
	}
	if(ans==INT_MAX) printf("Case #%d: SAFE\n",++test);
	else printf("Case #%d: %d\n",++test,ans*2);
}
int main() {
	int T; scanf("%d",&T);
	while(T--) solve();
	return 0;
}