#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 100100;
const int inf = 0x3f3f3f3f;

int n, m, S, T, head[maxn], len, f[maxn][2];
int deg[maxn];
bool vis[maxn];
struct edge {
	int to, next;
} edges[maxn << 2];

void add_edge(int u, int v) {
	edges[++len].to = v;
	edges[len].next = head[u];
	head[u] = len;
}

void bfs(int S, int t) {
	queue<int> q;
	q.push(S);
	f[S][t] = 0;
	while (q.size()) {
		int u = q.front();
		q.pop();
		for (int i = head[u]; i; i = edges[i].next) {
			int v = edges[i].to;
			if (f[v][t] == inf) {
				f[v][t] = f[u][t] + 1;
				q.push(v);
			}
		}
	}
}

void solve() {
	scanf("%d%d%d%d", &n, &m, &S, &T);
	len = 0;
	mems(vis, 0);
	mems(deg, 0);
	mems(head, 0);
	mems(f, 0x3f);
	while (m--) {
		int u, v;
		scanf("%d%d", &u, &v);
		add_edge(u, v);
		add_edge(v, u);
		++deg[u];
		++deg[v];
	}
	queue<int> q;
	for (int i = 1; i <= n; ++i) {
		vis[i] = (deg[i] == 1);
		if (vis[i]) {
			q.push(i);
		}
	}
	while (q.size()) {
		int u = q.front();
		q.pop();
		for (int i = head[u]; i; i = edges[i].next) {
			int v = edges[i].to;
			if (!vis[v] && (--deg[v]) == 1) {
				q.push(v);
			}
		}
	}
	bfs(S, 0);
	bfs(T, 1);
	for (int i = 1; i <= n; ++i) {
		if (!vis[i] && f[i][0] < f[i][1]) {
			puts("SAFE");
			return;
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		if (f[i][0] < f[i][1]) {
			ans = max(ans, f[i][1]);
		}
	}
	if (ans == inf) {
		puts("SAFE");
	} else {
		printf("%d\n", ans * 2);
	}
}

int main() {
	int T = 1;
	scanf("%d", &T);
	for (int t = 1; t <= T; ++t) {
		printf("Case #%d: ", t);
		solve();
	}
	return 0;
}