#include<bits/stdc++.h>
#define I cin
#define O cout
#define N int
#define L long long
#define V vector
#define F pair
#define P first
#define Q second
using namespace std;
void S(){
N n,m,A,B;I>>n>>m>>A>>B;--A,--B;
V<V<N>>e(n);
V<N>d(n);
for(N i=0;i<m;++i){
	N u,v;I>>u>>v;--u,--v;
	e[u].push_back(v),e[v].push_back(u);
	++d[u],++d[v];
}
queue<N>q;
for(N i=0;i<n;++i)if(d[i]==1)q.push(i);
while(q.size()){
	N u=q.front();q.pop();
	for(N v:e[u]){
		if(d[v]){
			--d[v],--d[u];
			if(!d[v])q.push(v);
		}
	}
}
V<N>lp;for(N u=0;u<n;++u)if(d[u])lp.push_back(u);
V dA(n,-1),dB(n,-1);
dA[A]=dB[B]=0;
q.push(A);
while(q.size()){
	N u=q.front();q.pop();
	for(N v:e[u])if(dA[v]==-1){
		dA[v]=dA[u]+1;
		q.push(v);
	}
}
q.push(B);
while(q.size()){
	N u=q.front();q.pop();
	for(N v:e[u])if(dB[v]==-1){
		dB[v]=dB[u]+1;
		q.push(v);
	}
}
if(dA[B]==-1)return O<<"SAFE\n",void();
for(N u:lp)if(dA[u]!=-1&&dA[u]<dB[u])
	return O<<"SAFE\n",void();
N ans=0;
for(N u=0;u<n;++u){
	if(dA[u]!=-1&&dA[u]<dB[u])ans=max(ans,dB[u]);
}O<<ans*2<<'\n';
}
signed main(){cin.tie(0)->sync_with_stdio(0);
N T;I>>T;
for(N i=1;i<=T;++i){O<<"Case #"<<i<<": ";S();}
}