#include <bits/stdc++.h>
#define st first
#define nd second
#define db double
#define re register
#define pb push_back
#define mk make_pair
//#define int long long
#define ldb long double
#define pii pair<int, int>
#define ull unsigned long long 
#define mst(a, b) memset(a, b, sizeof(a))
using namespace std;
const int N = 1e5 + 10;
inline int read()
{
	
  int s = 0, w = 1;
  char ch = getchar();
  while(ch < '0' || ch > '9') { if(ch == '-') w *= -1; ch = getchar(); }
  while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
  return s * w;
}
int T, n, m, A, Q, ans;
int st, ed, q[N], dir[N], dis[2][N];
bool vis[N], chk[N]; //是否是安全点 
vector<int> G[N];
inline void BFS(int s, int op)
{
	for(re int i = 1; i <= n; i++) dis[op][i] = -1;
	dis[op][s] = 0, st = 1, ed = 0, q[++ed] = s;
	while(st <= ed){
		int u = q[st]; st++;
		for(re int to : G[u])
			if(dis[op][to] == -1) dis[op][to] = dis[op][u] + 1, q[++ed] = to;
	}
}
inline void DFS(int u)
{
	chk[u] = true;
	if(G[u].size() == 1)
		ans = max(ans, dis[1][u]); //找到一个叶子然后不动 
	for(re int to : G[u])
		if(to != Q && !chk[to] && !vis[to] && dis[0][to] < dis[1][to]) DFS(to); 
}
inline void Sol(int Cas)
{
	n = read(), m = read(), A = read(), Q = read();
	for(re int i = 1; i <= n; i++) G[i].clear(), vis[i] = true, chk[i] = false, dir[i] = 0; 
	for(re int i = 1, x, y; i <= m; i++)
		x = read(), y = read(), G[x].pb(y), G[y].pb(x), dir[x]++, dir[y]++;
	st = 1, ed = 0;
	for(re int i = 1; i <= n; i++) if(dir[i] == 1) q[++ed] = i;
	while(st <= ed){
		int u = q[st];
		st++, vis[u] = false;
		for(re int to : G[u]){
			if(!vis[to]) continue;
			dir[to] -= 1;
			if(dir[to] == 1) q[++ed] = to;
		}
	}
	BFS(A, 0), BFS(Q, 1);
	if(dis[0][Q] == -1) { printf("Case #%d: SAFE\n", Cas); return; } //不在一个联通块 
	for(re int i = 1; i <= n; i++)
		if(vis[i] && dis[0][i] < dis[1][i]) { printf("Case #%d: SAFE\n", Cas); return; }
	ans = 0, DFS(A);
	printf("Case #%d: %d\n", Cas, 2 * ans);
}
signed main()
{
	T = read();
	for(re int Cas = 1; Cas <= T; Cas++) Sol(Cas);
	return 0;
}
/*
1
5 4 5 2
1 4
4 5
2 4
1 3
*/