#include<bits/stdc++.h>
using namespace std;
namespace IO_ER{
	#define LL long long
	#define db double
	#define ULL unsigned long long
	#define In inline
	#define f(a,b,i) for(int i=a;i<=b;i++)
	#define ff(a,b,i) for(int i=a;i<b;i++)
	#define f_(a,b,i) for(int i=a;i>=b;i--)
	#define ff_(a,b,i) for(int i=a;i>b;i--)
	typedef pair<int,int> Pi;
	int inf=0x3f3f3f3f;
	int INF=0x7fffffff;
	LL infll=0x3f3f3f3f3f3f3f3fll;
	LL INFll=0x7fffffffffffffffll;
	int FLAG_=0;
	char CHAR=0;
	template<typename T>void read(T &x){
		x=0;
		FLAG_=0;
		CHAR=getchar();
		while(CHAR<'0'||'9'<CHAR){
			if(CHAR=='-')FLAG_=1;
			CHAR=getchar();
		}
		while('0'<=CHAR&&CHAR<='9'){
			x=(x<<1)+(x<<3)+(CHAR^48);
			CHAR=getchar();
		}
		x=FLAG_?-x:x;
	}
	template<typename T,typename ...Args>void read(T &x,Args &...args){
		read(x);
		read(args...);
	}
}
using namespace IO_ER;

#define N 200500

int n,m;

vector<int>e[N];

int du[N];

int vis[N];

void ring(){
	queue<int>q;
	f(1,n,i){
		if(du[i]==1){
			vis[i]=1;
			q.emplace(i);	
		}
	}
	while(q.size()){
		int u=q.front();q.pop();
		for(auto v:e[u]){
			if(vis[v])continue;
			du[v]--;
			if(du[v]==1){
				vis[v]=1;
				q.emplace(v);
			}	
		}
	}
}

int dsa[N];
int dsb[N];

void bfs(int st,int *dis){
	f(1,n,i)dis[i]=inf;
	queue<int>q;
	q.emplace(st);
	dis[st]=0;
	while(q.size()){
		int u=q.front();q.pop();
		for(auto v:e[u]){
			if(dis[v]!=inf)continue;
			dis[v]=dis[u]+1;
			q.emplace(v);
		}
	}
}

int main(){
	int T;
	int X,Y;
	read(T);
	f(1,T,kkk){
		read(n,m,X,Y);
		f(1,n,i)e[i].clear();
		f(1,n,i)du[i]=0;
		f(1,n,i)vis[i]=0;
		int u,v;
		f(1,m,i){
			read(u,v);
			e[u].emplace_back(v);
			e[v].emplace_back(u);
			du[u]++;
			du[v]++;
		}
//		cout<<1<<endl;
		ring();	
//		f(1,n,i)cout<<vis[i]<<" ";
//		cout<<endl;
		bfs(X,dsa);
		bfs(Y,dsb);
		int ans=0;
		f(1,n,i){
			if(!vis[i]&&dsa[i]<dsb[i]){
				printf("Case #%d: SAFE\n",kkk);
				goto A;
			}
		}
		f(1,n,i){
			if(dsa[i]<dsb[i]){
				ans=max(ans,dsb[i]);
			}
		}
		if(ans==inf)printf("Case #%d: SAFE\n",kkk);
		else printf("Case #%d: %d\n",kkk,2*ans);
		A:;
	}
	return 0;
}