#include<bits/stdc++.h>
#include<queue>
#define N 100000
using namespace std;
int T,n,m,s,t,d[N+5];
vector<int> e[N+5];
unsigned dis[2][N+5];
bool save[N+5];
inline void bfs(int s,unsigned *dis)
{
	memset(dis+1,-1,n<<2),dis[s]=0;
	queue<int> q;q.push(s);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int y:e[x]) if(!~dis[y])
			dis[y]=dis[x]+1,q.push(y);
	}
}
inline void solve()
{
	queue<int> q;
	for(int i=1;i<=n;++i) if(d[i]==1) q.push(i);
	memset(save+1,1,n);
	while(!q.empty())
	{
		int x=q.front();q.pop(),save[x]=0;
		for(int y:e[x]) if((--d[y])==1) q.push(y);
	}
	if(!~dis[0][t]) return puts("SAFE"),void();
	unsigned ans=0;
	for(int i=1;i<=n;++i) if(dis[0][i]<dis[1][i])
	{
		if(save[i]) return puts("SAFE"),void();
		ans=max(ans,dis[1][i]);
	}
	printf("%u\n",ans*2);
}
int main()
{
	scanf("%d",&T);
	for(int test=1;test<=T;++test)
	{
		scanf("%d %d %d %d",&n,&m,&s,&t);
		for(int i=1;i<=n;++i) e[i].clear();
		memset(d+1,0,n<<2);
		for(int i=1,u,v;i<=m;++i)
		{
			scanf("%d %d",&u,&v);
			e[u].push_back(v),++d[u];
			e[v].push_back(u),++d[v];
		}
		printf("Case #%d: ",test);
		bfs(s,dis[0]),bfs(t,dis[1]),solve();
	}
	return 0;
}