#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 6e6+10,maxm = 6e6+10;
struct {
	int nxt,v;
}edge[maxm];
int deg[maxn],T,n,m,a,b,ec,head[maxn];
set<int> tag[maxn]; 
inline void addedge(int u,int v) {
	++deg[u];
	edge[++ec] = {head[u],v};
	head[u] = ec;
}
inline void clearedge(){
	memset(head,0,n + 10 << 4);
	memset(deg,0,n + 10 << 4);
	ec = 0;
	for(int i = 1;i <= n;++i) tag[i].clear();
}
inline void toposort(){
	static queue<int> q;
	for(int i = 1;i <= n;++i) if(deg[i] == 1) q.push(i);
	while(!q.empty()) {
		const int u = q.front();q.pop();
		for(int i = head[u];i;i = edge[i].nxt) {
			const int v = edge[i].v;
			if(--deg[v] == 1) q.push(v);
		}
	}
}
#define pb push_back
#define pii pair<int,int>
vector<int> sf;
int da[maxn],db[maxn],*dis;
bool vis[maxn];
inline void dij(int s){
	memset(dis,0x3f,n + 10 << 4);
	memset(vis,0,n + 10 << 4);
	static priority_queue<pii,vector<pii>,greater<pii>> pq;
	pq.push({dis[s] = 0,s});
	while(!pq.empty()) {
		int du,u;
		tie(du,u) = pq.top(); pq.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i = head[u];i;i=edge[i].nxt) {
			const int v = edge[i].v;
			if(dis[v] >dis[u] + 1) pq.push({dis[v] = du+1,v});
		}
	}
}
signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin>>T;
	for(int cas = 1;cas <= T;++cas) {
		int ans = 0;
		cout<<"Case #"<<cas<<": ";
		cin>>n>>m>>a>>b;
		clearedge();
		for(int i = 1,u,v;i<=m;++i) {
			cin>>u>>v;
			if(u != v && !tag[u].count(v))
				addedge(u,v),addedge(v,u),tag[u].insert(v);
		}
		toposort();
		dis = da, dij(a);
		dis = db, dij(b);
		for(int u = 1;u <= n;++u) if(deg[u] > 1 && da[u] < db[u]) {
			cout<<"SAFE";
			goto sb;
		}
		for(int u = 1;u <= n;++u) if(da[u] < db[u]) ans = max(ans,db[u]);
		cout<<(ans > 2 * n ? "SAFE" : to_string(ans*2));
		sb: cout<<'\n'; 
			
	} 
}