#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
constexpr int N=200010,inf=1e9;
vector<int> es[N];
int d1[N],d2[N];
void bfs(int s,int (&d)[N],int n)
{
	static bool vis[N];
	fill(d+1,d+n+1,inf);
	memset(vis+1,0,sizeof(bool)*n);
	vis[s]=true;d[s]=0;
	static queue<int> qq;
	qq.push(s);
	while(!qq.empty())
	{
		int u=qq.front();qq.pop();
		for(int v:es[u])
		{
			if(!vis[v])
			{
				d[v]=d[u]+1;
				vis[v]=true;
				qq.push(v);
			}
		}
	}
}
bool hc[N],vd[N];int dfn[N],dcnt,low[N];
void dfs(int u,int fa)
{
	vd[u]=true;dfn[u]=low[u]=++dcnt;
	for(int v:es[u])
	{
		if(v==fa)
			continue;
		if(dfn[v])
			low[u]=min(low[u],dfn[v]);
		else
			dfs(v,u),low[u]=min(low[u],low[v]);
	}
	if(low[u]<dfn[u])
		hc[u]=true;
}
int main()
{
	int TC;
	scanf("%d",&TC);
	for(int ti(1),n,m,A,Q;ti<=TC;++ti)
	{
		scanf("%d%d%d%d",&n,&m,&A,&Q);
		for(int i(1),u,v;i<=m;++i)
		{
			scanf("%d%d",&u,&v);
			es[u].push_back(v);es[v].push_back(u);
		}
		memset(hc,0,sizeof(hc));
		memset(vd,0,sizeof(vd));
		memset(dfn,0,sizeof(dfn));
		dcnt=0;
		bfs(A,d1,n);bfs(Q,d2,n);dfs(Q,0);
		if(d2[A]==inf)
		{
			printf("Case #%d: SAFE\n",ti);
			continue;
		}
		bool ok=false;
		// for(int i(1);i<=n;++i)
		// 	printf("%d,%d,%d ",hc[i],d1[i],d2[i]);
		// printf("\n");
		for(int i(1);i<=n;++i)
		if(d1[i]<d2[i] && hc[i])
			ok=true;
		if(ok)
		{
			printf("Case #%d: SAFE\n",ti);
			continue;
		}
		else
		{
			int ans=0;
			for(int i(1);i<=n;++i)
			if(d1[i]<d2[i])
				ans=max<int>(ans,d2[i]*2);
			printf("Case #%d: %d\n",ti,ans);
		}
		for(int i(1);i<=n;++i)
			es[i].clear();
	}
	return 0;
}