#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10,inf=1e9;
vector<int> G[maxn];
int n,m;
void bfs(int s,int *dis)
{
	for(int i=1;i<=n;i++)dis[i]=-1;
	dis[s]=0;
	queue<int> q;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int v:G[u])
			if(dis[v]==-1)
			{
				dis[v]=dis[u]+1;
				q.push(v);
			}
	}
	for(int i=1;i<=n;i++)
		if(dis[i]==-1)dis[i]=inf;
}
int Ax[maxn],Bx[maxn],A,B,D[maxn];
queue<int> q;
int deg[maxn];
bool safe[maxn];
int sp[maxn],tot;
void solve(int Caseid)
{
	scanf("%d%d%d%d",&n,&m,&A,&B);
	for(int i=1;i<=n;i++)G[i].clear(),deg[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);
		deg[u]++;
		deg[v]++; 
	} 
	for(int i=1;i<=n;i++)if(deg[i]==1)q.push(i);
	for(int i=1;i<=n;i++)safe[i]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		safe[u]=0;
		for(int v:G[u])
		{
			deg[v]--;
			if(deg[v]==1)q.push(v);
		}
	}
	tot=0;
	for(int i=1;i<=n;i++)if(safe[i])sp[++tot]=i;
	bfs(A,D);
	bfs(A,Ax);
	bfs(B,Bx);
	if(D[B]==inf)
		{printf("Case #%d: SAFE\n",Caseid);return;}
	for(int i=1;i<=tot;i++)
		if(Ax[sp[i]]<Bx[sp[i]])
			{printf("Case #%d: SAFE\n",Caseid);return;}
	int ans=0;
	for(int i=1;i<=n;i++)
		if(Bx[i]!=inf)ans=max(ans,Bx[i]*2);
	printf("Case #%d: %d\n",Caseid,ans);
	return;
}
int main()
{
	int T;
	scanf("%d",&T);
	for(int i=1;i<=T;i++)
		solve(i);
	return 0;
}