#include <bits/stdc++.h>
using namespace std;

#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define Check(a) freopen(a".in", "r", stdin), freopen(a".ans", "w", stdout)

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef long double ld;
typedef pair<int, int> pii;
#define mp make_pair
#define fi first
#define se second
#define eps 1e-10

const int mod = 1e9 + 7;
template <typename A>
inline int M(A x) {return x;}
template <typename A, typename ... B>
inline int M(A x, B ... args) {return 1ll * x * M(args ...) % mod;}

inline int Mi(const int &x) {return x >= mod ? x - mod : x;}
inline int Ad(const int &x) {return x < 0 ? x + mod : x;}
inline void mi(int &x, const int &y) {x += y; x >= mod && (x -= mod);}
inline void ad(int &x, const int &y) {x -= y; x < 0 && (x += mod);}

const int N = 2e5 + 7, INF = 1e9;

int n, m, X, Y, du[N], d[2][N];
bool vis[N];
vector<int> g[N];

inline void topo() {
	queue<int> q;
	for (int i = 1; i <= n; ++i) !du[i] && (q.push(i), vis[i] = 1);
	
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int v : g[u]) !vis[v] && !--du[v] && (q.push(v), vis[v] = 1);
	}
}

inline void bfs(int s, bool b) {
	for (int i = 1; i <= n; ++i) d[b][i] = INF;
	queue<int> q; q.push(s), d[b][s] = 0;
	
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int v : g[u]) d[b][v] == INF && (q.push(v), d[b][v] = d[b][u] + 1);
	}
}

inline void mian(int I) {
	cout << "Case #" << I << ": ";
	cin >> n >> m >> X >> Y;
	for (int i = 1; i <= n; ++i) g[i].clear(), vis[i] = 0;
	for (int i = 1, u, v; i <= m; ++i) 
		cin >> u >> v, g[u].push_back(v), g[v].push_back(u);
	for (int i = 1; i <= n; ++i) du[i] = g[i].size() - 1;
	topo();
	bfs(X, 0); bfs(Y, 1);
	
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		if (!vis[i] && d[0][i] < d[1][i]) return (void)(cout << "SAFE\n");
		if (d[0][i] < d[1][i]) {
			if (d[1][i] == INF) return (void)(cout << "SAFE\n");
			ans = max(ans, d[1][i]);
		}
	}
	
	cout << ans + ans << "\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int T; cin >> T; for (int i = 1; i <= T; ++i) mian(i);

	return 0;
}