// Problem: #4511. Wonderland Chase
// Contest:
// URL: https://qoj.ac/problem/4511
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <bits/stdc++.h>
using namespace std;
#define gh() getchar()
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;
}
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
vector<int> G[maxn];
int disa[maxn], disb[maxn];
int a, b, n, m;
queue<int> q;
void bfs1() {
    q.emplace(a);
    disa[a] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : G[u]) {
            if (!disa[v]) {
                disa[v] = disa[u] + 1;
                q.push(v);
            }
        }
    }
}
void bfs2() {
    q.emplace(b);
    disb[b] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : G[u]) {
            if (!disb[v]) {
                disb[v] = disb[u] + 1;
                q.push(v);
            }
        }
    }
}
bool vis[maxn], safe[maxn];
int deg[maxn];
void solve(int cas) {
    n = read(), m = read(), a = read(), b = read();
    for (int i = 1; i <= n; i++) G[i].clear(), deg[i] = disa[i] = disb[i] = 0;
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read();
        G[u].emplace_back(v);
        G[v].emplace_back(u);
        deg[u]++;
        deg[v]++;
    }
    bfs1();
    bfs2();
    if (disb[a] == 0) {
        printf("Case #%d: SAFE\n", cas);
        return;
    }
    for (int i = 1; i <= n; i++) {
        safe[i] = (deg[i] != 1);
        if (!safe[i]) {
            q.emplace(i);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : G[u]) {
            deg[v]--;
            if (deg[v] == 1 && safe[v]) {
                safe[v] = 0;
                q.emplace(v);
            }
        }
    }
    // for (int i = 1; i <= n; i++) printf("%d ", disa[i]);
    // printf("\n");
    // for (int i = 1; i <= n; i++) printf("%d ", disb[i]);
    // printf("\n");
    // for (int i = 1; i <= n; i++) printf("%d ", (int)safe[i]);
    // printf("\n");
    int dep = 0;
    for (int i = 1; i <= n; i++) {
        if (safe[i] && disa[i] < disb[i]) {
            printf("Case #%d: SAFE\n", cas);
            return;
        }
        if (disa[i] < disb[i]) {
            dep = max(dep, disb[i]);
        }
    }
    printf("Case #%d: %d\n", cas, (dep - 1) * 2);
}
int t;
int main() {
    scanf("%d", &t);
    for (int i = 1; i <= t; i++) {
        solve(i);
    }
}