#include <bits/stdc++.h>
#define N 100010

using namespace std;

int n, m;
vector <int> g[N];
int in[N], dis[2][N], vis[N];

const int inf = 0x7f7f7f7f;

inline int read() {
	char ch = getchar(); int x = 0, f = 1;
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
	return x * f;
}

queue <int> q;

void bfs(int S, int *dis) {
	dis[S] = 0;
	q.push(S);
	while(!	q.empty()) {
		int u = q.front(); q.pop();
		
		for(int v : g[u]) {
			
			
			if(dis[v] == inf) {
				dis[v] = dis[u] + 1;
				q.push(v);
			}
		}
	}
}

int main() {
	int t = read();
	for(int i = 1; i <= t; i++) {
		int S, T;
		n = read(), m = read(), S = read(), T = read();
		
		for(int i = 1; i <= n; i++)
			g[i].clear(), in[i] = 0, dis[0][i] = dis[1][i] = 0x7f7f7f7f, vis[i] = 0;
		
		for(int i = 1; i <= m; i++) {
			int u = read(), v = read();
			g[u].push_back(v);
			g[v].push_back(u);
			in[u]++;
			in[v]++;
		}
		
		for(int i = 1; i <= n; i++)
			if(in[i] == 1)
				q.push(i);
		
		while(!q.empty()) {
			int u = q.front(); q.pop();
			vis[u] = 1;
			for(int v : g[u]) {
				--in[v];
				if(in[v] == 1)
					q.push(v);
			}
		}
		
		
		bfs(S, dis[0]);
		bfs(T, dis[1]);
		
		int flag = 0;
		for(int i = 1; i <= n; i++) {
			if(!vis[i] && dis[0][i] < dis[1][i]) {
				flag = 1;
			} 
		}
		
		if(dis[1][S] == inf)
			flag = 1;
		if(flag) {
			cout << "Case #" << i << ": SAFE" << endl;
			continue; 
		}
		
		int maxn = 0;
		for(int i = 1; i <= n; i++) {
			if(vis[i] && dis[0][i] != inf && dis[1][i] != inf && dis[0][i] < dis[1][i])
				maxn = max(maxn, dis[1][i]);
		}
		
		cout << "Case #" << i << ": " << maxn * 2 << endl;	
		
	}
}