#include<bits/stdc++.h>
using namespace std;
namespace IO{
	template<typename T>inline bool read(T &x){
		x=0;
		char ch=getchar();
		bool flag=0,ret=0;
		while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
		while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(),ret=1;
		x=flag?-x:x;
        return ret;
	}
	template<typename T,typename ...Args>inline bool read(T& a,Args& ...args){
	    return read(a)&&read(args...);
	}
	template<typename T>void prt(T x){
		if(x>9) prt(x/10);
		putchar(x%10+'0');
	}
	template<typename T>inline void put(T x){
		if(x<0) putchar('-'),x=-x;
		prt(x);
	}
	template<typename T>inline void put(char ch,T x){
		if(x<0) putchar('-'),x=-x;
		prt(x);
		putchar(ch);
	}
	template<typename T,typename ...Args>inline void put(T a,Args ...args){
	    put(a);
		put(args...);
	}
	template<typename T,typename ...Args>inline void put(const char ch,T a,Args ...args){
	    put(ch,a);
		put(ch,args...);
	}
	inline void put(string s){
		for(int i=0,sz=s.length();i<sz;i++) putchar(s[i]);
	}
	inline void put(const char* s){
		for(int i=0,sz=strlen(s);i<sz;i++) putchar(s[i]);
	}
}
using namespace IO;
#define N 200005
#define inf 0x3f3f3f3f
int T,n,m,A,B,deg[N];
vector<int> e[N];
struct dsu{
	int fa[N];
	dsu(){memset(fa,0,sizeof(fa));}
	inline void prework(){
		for(int i=1;i<=n;i++) fa[i]=i;
	}
	inline int getf(int x){
		return fa[x]==x?x:fa[x]=getf(fa[x]);
	}
	inline void merge(int x,int y){
		x=getf(x),y=getf(y);
		if(x!=y) fa[x]=y;
	}
}D;
int f[N],g[N];
inline void solve(){
	queue<int> q;
	read(n,m,A,B),D.prework();
	for(int i=1;i<=n;i++) e[i].clear(),f[i]=g[i]=inf;
	for(int i=1,u,v;i<=m;i++)
		read(u,v),D.merge(u,v),e[u].emplace_back(v),e[v].emplace_back(u);
	for(int i=1;i<=n;i++){
		deg[i]=e[i].size();
		if(deg[i]==1) q.push(i);
	}
	if(D.getf(A)!=D.getf(B)) return puts("SAFE"),void();
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(auto v:e[x])
			if(--deg[v]==1) q.push(v);
	} 
	q.push(A),f[A]=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(auto v:e[x])
			if(f[v]>f[x]+1) q.push(v),f[v]=f[x]+1;
	}
	q.push(B),g[B]=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(auto v:e[x])
			if(g[v]>g[x]+1) q.push(v),g[v]=g[x]+1;
	}
	for(int i=1;i<=n;i++)
		if(deg[i]>1&&f[i]<g[i]) return puts("SAFE"),void();
	int ans=0;
	for(int i=1;i<=n;i++) 
		if(f[i]<g[i]) ans=max(ans,g[i]<<1);
	put('\n',ans);
}
int main(){
	read(T);
	for(int test=1;test<=T;test++)
		put("Case #"),put(':',test),putchar(' '),solve(); 
	return 0;
}