// Google Code Jam 2022 World Finals
// Problem A. Wonderland Chase
#include <bits/stdc++.h>

using LL = long long;
using ULL = unsigned LL;

constexpr ULL E(long double x, int y) {
    while (y--) x *= 10;
    return x;
}
constexpr ULL SIZE(long double x, int y) {return E(x, y) + 5;}

const int inf32 = E(1, 9) + 5;
const LL inf64 = E(1, 18) + 5;

bool vis[SIZE(1, 5)];
std::multiset<int> graph[SIZE(1, 5)];
int n, m, s, t, deg[SIZE(1, 5)], dis[2][SIZE(1, 5)];

int main() {
    int data_count;
    scanf("%d", &data_count);
    for (int data = 1; data <= data_count; data++) {
        scanf("%d%d%d%d", &n, &m, &s, &t);
        for (int i = 1; i <= n; i++) {
            deg[i] = 0;
            vis[i] = false;
            dis[0][i] = dis[1][i] = -1;
            graph[i].clear();
        }
        for (int i = 1; i <= m; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            graph[x].insert(y);
            graph[y].insert(x);
            deg[x]++;
            deg[y]++;
        }
        std::queue<int> que;
        for (int i = 1; i <= n; i++)
            if (deg[i] == 1)
                que.push(i);
        while (que.size()) {
            int u = que.front();
            que.pop();
            vis[u] = true;
            for (int v : graph[u])
                if (--deg[v] == 1)
                    que.push(v);
        }
        que.push(s);
        dis[0][s] = 0;
        while (que.size()) {
            int u = que.front();
            que.pop();
            for (int v : graph[u]) {
                if (dis[0][v] != -1) continue;
                dis[0][v] = dis[0][u] + 1;
                que.push(v);
            }
        }
        que.push(t);
        dis[1][t] = 0;
        while (que.size()) {
            int u = que.front();
            que.pop();
            for (int v : graph[u]) {
                if (dis[1][v] != -1) continue;
                dis[1][v] = dis[1][u] + 1;
                que.push(v);
            }
        }
        if (dis[1][s] == -1)
            printf("Case #%d: SAFE\n", data);
        else {
            bool flag = false;
            for (int i = 1; i <= n; i++) {
                if (!vis[i] && dis[0][i] < dis[1][i]) {
                    printf("Case #%d: SAFE\n", data);
                    flag = true;
                }
            }
            if (!flag) {
                int max = 0;
                for (int i = 1; i <= n; i++) {
                    if (dis[0][i] < dis[1][i])
                        max = std::max(max, dis[1][i]);
                }
                printf("Case #%d: %d\n", data, 2 * max);
            }
        }
    }
    return 0;
}