#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
// #define int ll
#define Inf 0x3f3f3f3f
using namespace std;
const int N=2e5+60,M=1e6+20,mod=998244353;
inline int read(){
    int d=0,f=1;char x=getchar();
    while(x<'0'||x>'9'){if(x=='-'){f=-1;}x=getchar();}
    while(x>='0'&&x<='9'){d=(d<<1)+(d<<3)+(x-48);x=getchar();}
    return d*f;
}
struct Edge{int v,nxt;}edge[M<<1];
int head[N],ecnt;
inline void add(int u,int v){
    edge[++ecnt]=(Edge){v,head[u]};
    head[u]=ecnt;
}
int n,m,dis[2][N],sa,sb,deg[N];
bool vis[N];
void get(int s,int u){
    queue<int> q;
    for(int i=1;i<=n;i++) dis[u][i]=Inf;
    dis[u][s]=0;q.push(s);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=edge[i].nxt){
            int y=edge[i].v;
            if(dis[u][y]==Inf){
                dis[u][y]=dis[u][x]+1,q.push(y);
            }
        }
    }
    // printf("%d\n",u);
    // for(int i=1;i<=n;i++) printf("%d ",dis[u][i]);puts("");
}
void solve(){
    queue<int> q;
    get(sa,0);get(sb,1);
    for(int i=1;i<=n;i++){
        if(dis[1][i]==Inf&&dis[0][i]!=Inf) return puts("SAFE"),void();
    }
    for(int i=1;i<=n;i++) if(deg[i]==1) q.push(i),vis[i]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=edge[i].nxt){
            int v=edge[i].v;
            if(!vis[v]&&(--deg[v])==1) q.push(v),vis[v]=1;
        }
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]&&dis[0][i]<dis[1][i]) return puts("SAFE"),void();
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(dis[0][i]<dis[1][i]) ans=max(ans,dis[1][i]);
    }
    printf("%lld\n",ans*2);
}
signed main(){
    int t=read();
    for(int i=1;i<=t;i++){
        memset(head,0,sizeof(head));ecnt=0;
        memset(deg,0,sizeof(deg));memset(vis,0,sizeof(vis));
        n=read();m=read();sa=read();sb=read();
        for(int j=1;j<=m;j++){
            int u=read(),v=read();
            add(u,v);add(v,u);deg[v]++;deg[u]++;
        } 
        printf("Case #%d: ",i);solve();
    }
    return 0;
}
////7950