#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int n,die[maxn],m,deg[maxn],dis[maxn][2],sa,sb;
vector<int>ed[maxn];
void bfs(int x,int fl){
    queue<int>Q;
    Q.push(x);
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        for(auto v:ed[u]){
            if(v!=x&&!dis[v][fl])Q.push(v),dis[v][fl]=dis[u][fl]+1;
        }
    }
}
void sol(){
    cin>>n>>m>>sa>>sb;
    for(int i=1;i<=n;i++)ed[i].clear(),dis[i][0]=dis[i][1]=0,die[i]=0,deg[i]=0;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        ed[u].push_back(v),ed[v].push_back(u);
        deg[v]++,deg[u]++;
    }
    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();
        die[u]=1;
        for(auto v:ed[u]){
            deg[v]--;
            if(!die[v]&&deg[v]==1)Q.push(v);
        }
    }
    bfs(sa,0),bfs(sb,1);
    if(!dis[sa][1]){
        cout<<"SAFE"<<"\n";
        return;
    }
    int maxv=0;
    for(int i=1;i<=n;i++){
        if(dis[i][0]<dis[i][1]){
            maxv=max(maxv,dis[i][1]);
            if(!die[i]){
                cout<<"SAFE"<<"\n";
                return;
            }
        }
    }
    cout<<maxv*2<<"\n";
}
int main(){
    cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);
    int tc;
    cin>>tc;
    for(int i=1;i<=tc;i++){
        cout<<"Case #"<<i<<": ";
        sol();
    }
    return 0;
}