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

namespace vbzIO {
    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
    #define pc putchar
    #define pi pair<int, int>
    #define tu3 tuple<int, int, int>
    #define tu4 tuple<int, int, int, int>
    #define mp make_pair
    #define mt make_tuple
    #define fi first
    #define se second
    #define pb push_back
    #define ins insert
    #define era erase
    inline int read () {
        char ch = gh();
        int 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;
    }
    inline void write(int x) {
        if (x < 0) {
            x = ~(x - 1);
            putchar('-');
        }
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
}
using vbzIO::read;
using vbzIO::write;

const int maxn = 1e5 + 100;
int T, n, m, s, t, vis[maxn], dis[maxn][2], d[maxn];
vector<int> g[maxn];

void bfs(int x, int op) {
	queue<int> q;
	q.push(x), dis[x][op] = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int v : g[u]) 
			if (dis[v][op] == 1e9) dis[v][op] = dis[u][op] + 1, q.push(v);
	}
}

void solve(int tp) {
	n = read(), m = read(), s = read(), t = read();
	for (int i = 1; i <= n; i++) d[i] = 0, g[i].clear();
	for (int i = 1, u, v; i <= m; i++) {
		u = read(), v = read();
		g[u].pb(v), g[v].pb(u), d[u]++, d[v]++;
	}
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		vis[i] = (d[i] != 1), dis[i][0] = dis[i][1] = 1e9;
		if (!vis[i]) q.push(i);
	}
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int v : g[u]) {
			d[v]--;
			if (d[v] == 1 && vis[v]) q.push(v), vis[v] = 0; 
		}
	}
	bfs(s, 0), bfs(t, 1);
	for (int i = 1; i <= n; i++)
		cerr << dis[i][0] << " " << dis[i][1] << endl;
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) continue;
		cerr << i << endl;
		if (dis[i][0] < dis[i][1]) return printf("Case #%d: SAFE\n", tp), void();
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) 
		if (dis[i][0] < dis[i][1])
			ans = max(ans, dis[i][1]);
	printf("Case #%d: %d\n", tp, ans * 2);
}

int main() {
	T = read();
	int tp = 0;
	while (T--) solve(++tp);
	return 0;
}
/*
1
6 5 1 6
1 4
1 2
5 6
3 5
2 4
*/