#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,INF=1e9;
int T_,n,m,S,T,ans;
vector <int> G[N];
int in[N];
queue <int> q;

void bfs(int *dis,int st){
	for(int i=1;i<=n;i++) dis[i]=INF;
	dis[st]=0;
	while(q.size()) q.pop();
	q.push(st);
	
	while(q.size()){
		int u=q.front(); q.pop();
		for(int v: G[u]){
			if(dis[v]==INF) dis[v]=dis[u]+1,q.push(v);
		}
	}
}

int f[N],g[N];

bool vis[N];
void dfs(int u){
	if(f[u]>=g[u] || vis[u]) return ;
	vis[u]=1;
	if(in[u]>1) ans=INF;
	else ans=max(ans,g[u]);
	for(int v: G[u]){
		dfs(v);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>T_;
	for(int _=1;_<=T_;_++){
		ans=0;
		cin>>n>>m>>S>>T;
		for(int i=1;i<=n;i++) G[i].clear(),in[i]=vis[i]=0;
		for(int i=1;i<=m;i++){
			int u,v; scanf("%d%d",&u,&v);
			G[u].push_back(v);
			G[v].push_back(u);
			in[u]++,in[v]++;
		}
		
		for(int i=1;i<=n;i++)
			if(in[i]==1) q.push(i);
		while(q.size()){
			int u=q.front(); q.pop();
			for(int v: G[u]){
				in[v]--;
				if(in[v]==1) q.push(v);
			}
		}
		
		bfs(f,S);
		bfs(g,T);
		
		dfs(S);
		printf("Case #%d: ",_);
		if(ans==INF) printf("SAFE\n");
		else printf("%d\n",ans*2);
	}
	
}