#include<bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
const int maxn=2e5+7;
int T;
int n,m;
int cnt,head[maxn],to[maxn<<1],nxt[maxn<<1];
void add(int u,int v){
	++cnt;
	to[cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
int dis[2][maxn];
int dfn[maxn],low[maxn];
int tot;
int tim;
stack<int>st;
vector<int>edcc[maxn];
void tarjan(int u,int fa){
	st.push(u);
	dfn[u]=low[u]=++tim;
	for(ri e=head[u];e;e=nxt[e]){
		int v=to[e];
		if(v==fa)continue;
		if(dfn[v]){
			low[u]=min(low[u],dfn[v]);
			continue;
		} 
		tarjan(v,u);
		low[u]=min(low[u],low[v]);
		if(low[v]>dfn[u]){
			++tot;
			while(st.top()!=v){
				edcc[tot].emplace_back(st.top());
				st.pop();
			}
			edcc[tot].emplace_back(st.top());
			st.pop();
		}
	}
}
int a,b;
bool vis[maxn];
void get_dis(int u,int p){
	queue<int>q;
	q.push(u);
	memset(dis[p],0x3f,sizeof(dis[p]));
	dis[p][u]=0;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(ri e=head[u];e;e=nxt[e]){
			int v=to[e];
			if(dis[p][u]+1<dis[p][v]){
				dis[p][v]=dis[p][u]+1;
				q.push(v);
			}
		}
	}
}
void clear(){
	memset(head,0,sizeof(head));
	memset(to,0,sizeof(to));
	memset(nxt,0,sizeof(nxt));
	cnt=0;tim=0;
	for(ri i=1;i<=tot;i++){
		edcc[i].clear();
	}
	memset(dis,0,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
}
void solve(int now){
	cin>>n>>m>>a>>b;
	for(ri i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);add(v,u);
	}
	for(ri i=1;i<=n;i++){
		tarjan(i,0);
		++tot;
		while(!st.empty()){
			edcc[tot].emplace_back(st.top());
			st.pop();
		}
	}
	for(ri i=1;i<=tot;i++){
		if(edcc[i].size()>=3){
			for(auto x:edcc[i]){
				vis[x]=1;
			}
		}
	}
	get_dis(a,0);
	get_dis(b,1);
	if(dis[0][b]>m){
		cout<<"Case #"<<now<<": SAFE\n";
		return;
	}
	for(ri i=1;i<=n;i++){
		if(dis[0][i]<dis[1][i]&&vis[i]){
			cout<<"Case #"<<now<<": SAFE\n";
			return;
		}
	}
	int ans=0;
	for(ri i=1;i<=n;i++){
		if(dis[0][i]<dis[1][i]){
			ans=max(ans,dis[1][i]);
		}
	}
	cout<<"Case #"<<now<<": "<<ans*2<<endl;
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>T;
	for(ri i=1;i<=T;i++){
		solve(i);
		clear();
	}
	return 0;
}