#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define mp make_pair
#define ll long long
const int mod = 1e9+7;
const int maxn = 1e6+10;

namespace IO{
	void openfile(){
		#ifndef ONLINE_JUDGE
		freopen("in.in","r",stdin);
		freopen("out.out","w",stdout);
		#endif
	}

	int add(int x,int y){
		x+=y;
		if(x>=mod)
			x-=mod;
		return x;
	}

	int sub(int x,int y){
		x-=y;
		if(x<0)
			x+=mod;
		return x;
	}

	inline int read(){
		int x = 0,f = 0;
		char c = getchar();
		while(!isdigit(c))
			f|=c=='-',c = getchar();
		while(isdigit(c))
			x = x*10+c-'0',c = getchar();
		if(f)x = -x;
		return x;
	}
}
using namespace IO;

int T;
int n,m,A,B,vis[maxn],in[maxn],f[maxn];
int dis1[maxn],dis2[maxn],dis[maxn];
vector<int>e[maxn];

int find(int x){
	if(x==f[x])return x;
	return f[x] = find(f[x]);
}

void merge(int x,int y){
	x = find(x),y = find(y);
	f[x] = y;
}

void dij(int s){
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=n;i++)
		vis[i] = 0;
	priority_queue<pii,vector<pii>,greater<pii> >q;
	q.push(mp(0,s)),dis[s] = 0;
	while(!q.empty()){
		int x = q.top().second;
		q.pop();
		if(vis[x])
			continue;
		vis[x] = 1;
		for(int i=0;i<e[x].size();i++){
			int v = e[x][i];
			if(dis[v]>dis[x]+1)
				dis[v] = dis[x]+1,q.push(mp(dis[v],v));
		}
	}
}

void solve(int num){
	n = read(),m = read(),A = read(),B = read();
	for(int i=1;i<=n;i++)
		f[i] = i,in[i] = 0,e[i].clear();
	for(int i=1;i<=m;i++){
		int x = read(),y = read();
		e[x].push_back(y),e[y].push_back(x);
		merge(x,y);
		in[x]++,in[y]++;
	}
	printf("Case #%d: ",num);
	if(find(A)!=find(B)){
		puts("SAFE");
		return;
	}
	queue<int>q;
	for(int i=1;i<=n;i++)
		if(in[i]==1)
			q.push(i);
	dij(A);
	for(int i=1;i<=n;i++)
		dis1[i] = dis[i];
	dij(B);
	for(int i=1;i<=n;i++)
		dis2[i] = dis[i],vis[i] = 0;
//	for(int i=1;i<=n;i++)
//		cout<<dis1[i]<<' '<<dis2[i]<<endl;
	while(!q.empty()){
		int x = q.front();
		q.pop();
		vis[x] = 1;
		for(int i=0;i<e[x].size();i++){
			int v = e[x][i];
			in[v]--;
			if(in[v]==1)
				q.push(v);
		}
	}
	for(int i=1;i<=n;i++){
		if(dis1[i]<dis2[i]&&!vis[i]){
			puts("SAFE");
			return;
		}
	}
//	for(int i=1;i<=n;i++)
//		if(!vis[i])
//			cout<<i<<endl;
	int ans = 0;
	for(int i=1;i<=n;i++){
		if(dis1[i]<dis2[i])
			ans = max(ans,dis2[i]);
	}
	printf("%d\n",ans<<1);
}

signed main(){
//	openfile();
	T = read();
	for(int i=1;i<=T;i++)
		solve(i);
	return 0;
}

/*

1
2 1 1 2
1 2

*/