#include<bits/stdc++.h>
using namespace std;
int n,m,A,B;
vector<int> edge[100005];
int deg[100005];
int disA[100005],disB[100005];
int vis[100005];
queue<int> que;
int main(){
	int _;scanf("%d",&_);
	for(int __=1;__<=_;__++){
		scanf("%d%d%d%d",&n,&m,&A,&B);
		for(int i=1;i<=n;i++)deg[i]=0,edge[i].clear();
		for(int i=1;i<=m;i++){
			int x,y;scanf("%d%d",&x,&y);
			edge[x].push_back(y);
			edge[y].push_back(x);
			deg[x]++,deg[y]++;
		}
		memset(vis,0,sizeof(vis));
		memset(disA,0x3f,sizeof(disA));
		disA[A]=0;vis[A]=1;
		que.push(A);
		while(!que.empty()){
			int x=que.front();que.pop();
			for(int y:edge[x])if(!vis[y])disA[y]=disA[x]+1,vis[y]=1,que.push(y);
		}
		memset(vis,0,sizeof(vis));
		memset(disB,0x3f,sizeof(disB));
		disB[B]=0;vis[B]=1;
		que.push(B);
		while(!que.empty()){
			int x=que.front();que.pop();
			for(int y:edge[x])if(!vis[y])disB[y]=disB[x]+1,vis[y]=1,que.push(y);
		}
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;i++)if(deg[i]==1)que.push(i),vis[i]=1;
		while(!que.empty()){
			int x=que.front();que.pop();
			for(int y:edge[x])if(!vis[y]){
				deg[y]--;
				if(deg[y]==1)que.push(y),vis[y]=1;
			}
		}
		printf("Case #%d: ",__);
		if(disA[B]==0x3f3f3f3f){
			puts("SAFE");
			continue;
		}
		int ans=0;
		for(int i=1;i<=n;i++)if(!vis[i]&&disA[i]<disB[i]){ans=1;break;}
		if(!ans){
			for(int i=1;i<=n;i++)if(disA[i]<disB[i])ans=max(ans,disB[i]);
			printf("%d\n",ans);
		}else puts("SAFE");
	}
	return 0;
}