#pragma GCC optimize("Ofast")
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>

#define pb push_back

namespace IO {
	template<typename T> inline void rd(T &x) {
		x = 0; bool f = 0; char c = getchar();
		while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
		while ('0' <= c && c <= '9') x = x * 10 + (c - '0'), c = getchar();
		x = f ? -x : x;
	}
	template<typename T, typename ...Args> inline void rd(T &x, Args& ...args) { rd(x), rd(args...); }
	template<typename T> inline void wt(T x, char c) {
		int stk[114], top = 0;
		if (x < 0) x = -x, putchar('-');
		do stk[ ++ top] = x % 10, x /= 10; while (x);
		while (top) putchar(stk[top -- ] + '0');
		putchar(c);
	}
}
using namespace IO;
using namespace std;

const int INF = 1e9;
const int N = 1e5 + 7;
int n, m, s, t;
int deg[N];
bool st[N];
int dist[N][2];
vector<int> g[N];

inline void bfs(int s, int x) {
	queue<int> q;
	q.push(s);
	dist[s][x] = 0;
	while (q.size()) {
		int u = q.front();
		q.pop();
		for (int v : g[u]) {
			if (dist[v][x] > dist[u][x] + 1) {
				dist[v][x] = dist[u][x] + 1;
				q.push(v);
			}
		}
	}
}

inline void solve() {
	rd(n, m, s, t);
	while (m -- ) {
		int u, v; rd(u, v);
		g[u].pb(v), g[v].pb(u);
		deg[u] ++ , deg[v] ++ ;
	}
	queue<int> q;
	for (int i = 1; i <= n; i ++ ) {
		if(deg[i] == 1) st[i] = 1, q.push(i);
	}
	while (q.size()) {
		int u = q.front();
		q.pop();
		for (int v : g[u]) {
			if (st[v]) continue;
			if (( -- deg[v]) == 1) st[v] = 1, q.push(v);
		}
	}
	bfs(s, 0), bfs(t, 1);
	bool flag = (dist[t][0] == INF);
	for (int u = 1; u <= n; u ++ ) {
		if (!st[u] && dist[u][0] < dist[u][1]) flag = 1;
	}
	if (flag) puts("SAFE");
	else {
		int res = 0;
		for (int u = 1; u <= n; u ++ ) {
			if (st[u] && dist[u][0] < dist[u][1] && dist[u][1] != INF) res = max(res, dist[u][1]); 
		}
		wt(res * 2, '\n');
	}
	for (int i = 1; i <= n; i ++ ) g[i].clear(), deg[i] = 0, st[i] = 0, dist[i][0] = dist[i][1] = INF;
}

int main() {
	#ifndef ONLINE_JUDGE
	freopen("in.in", "r", stdin);
	freopen("out.out", "w", stdout);
	#endif
	for (int i = 1; i < N; i ++ ) dist[i][0] = dist[i][1] = INF;
	int T; rd(T);
	for (int i = 1; i <= T; i ++ ) {
		printf("Case #%d: ", i);
		solve();
	}
	return 0;
}