#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define LL long long
#define writesp(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n')
#define FileIO(ch) freopen(ch".in", "r", stdin), freopen(ch".out", "w", stdout)
using namespace std;

namespace IO {
    char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
    inline long long read() {
        char ch = gh();
        long long x = 0;
        bool t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? ~(x - 1) : x;
    }
    template <typename _Tp>
    inline void write(_Tp x) {
    	static char stk[64], *top = stk;
        if (x < 0) {
            x = ~(x - 1);
            putchar('-');
        }
        do *top++ = x % 10, x /= 10;
        while (x);
        while (top != stk) putchar((*--top) | 48);
    }
}

using IO::read;
using IO::write;

const int maxn(1e5 + 7), maxm(2e5 + 7);
int n, m, head[maxn], tot, dA[maxn], dB[maxn], sA, sB, deg[maxn];
struct edge {
	int v, nxt;
} e[maxm << 1];

inline void add_edge (int u, int v) {
	e[++tot] = {v, head[u]};
	head[u] = tot;
}

namespace DSU {
	int fa[maxn], sz[maxn];
	inline void init () {
		for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
	}
	inline int find (int x) {
		return x == fa[x] ? x : fa[x] = find(fa[x]);
	}
	inline void merge (int x, int y) {
		x = find(x), y = find(y);
		if (x == y) return;
		if (sz[x] > sz[y]) swap(x, y);
		fa[x] = y, sz[y] += sz[x];
	}
}

inline void bfs (int S, int *d) {
	queue<int> q;
	q.push(S), d[S] = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].v;
			if (d[v] == 1e9) d[v] = d[u] + 1, q.push(v);	 
		}
	}
}

inline void slv (int Case) {
	n = read(), m = read(), sA = read(), sB = read(), tot = 0;
	memset(head, 0, sizeof(int) * (n + 1));
	memset(deg, 0, sizeof(int) * (n + 1));
	DSU::init();
	for (int i = 1, u, v; i <= m; i++) {
		u = read(), v = read();
		add_edge(u, v);
		add_edge(v, u);
		DSU::merge(u, v);
		++deg[u], ++deg[v];
	}
	if (DSU::find(sA) != DSU::find(sB)) {
		printf("Case #%d: SAFE\n", Case);
		return;
	}
	for (int i = 1; i <= n; i++) dA[i] = dB[i] = 1e9;
	bfs(sA, dA), bfs(sB, dB);
	queue<int> q;
	for (int i = 1; i <= n; i++) if (deg[i] == 1) q.push(i);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].v;
			--deg[v];
			if (deg[v] == 1) q.push(v);
		}
	}
	for (int i = 1; i <= n; i++) 
		if (deg[i] > 1 && dA[i] < dB[i]) 
			return printf("Case #%d: SAFE\n", Case), void();
	int ans = 0;
	for (int i = 1; i <= n; i++)
		if (dA[i] < dB[i])
			ans = max(ans, dB[i]);
	printf("Case #%d: %d\n", Case, ans << 1); 
}

int main() {
	int T = read();
	for (int i = 1; i <= T; i++) slv(i);
}
// I love WHQ!