#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1e5 + 5, M = 2e5 + 5;
int n,m,a,b,T;
int head[N],to[M*2],nxt[M*2],cnt;
int dfn[N],low[N],tim;
int disa[N],disb[N],visa[N],visb[N];
int h[N];
queue<int> q;
void add(int u,int v) {
	to[++cnt] = v;
	nxt[cnt] = head[u];
	head[u] = cnt;
} 
int dfs(int u,int f) {
	dfn[u] = low[u] = ++tim;
	low[u] += 1;
	for(int e = head[u]; e; e = nxt[e]) {
		int v = to[e];
		if(v == f) continue;
		if(!dfn[v]) low[u] = min(dfs(v,u), low[u]);
		else low[u] = min(dfn[v], low[u]);
	}
	if(low[u] <= dfn[u]) h[u] = 1;
	return low[u];
}
void bfs(int s,int dis[],int vis[]) {
	q.push(s);
	dis[s] = 0;
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int e = head[u]; e; e = nxt[e]) {
			int v = to[e];
			if(dis[u] + 1 < dis[v]) {
				dis[v] = dis[u] + 1;
				q.push(v);
			}
		}
	}
	return;
} 
void slove(int T) {
	cin>>n>>m>>a>>b;
	for(int i=1,u,v;i<=m;++i) {
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	dfs(b,0);
	for(int i=1;i<=n;++i) {
		cout<<h[i];
	}cout<<endl;
	bfs(b,disb,visb);
	for(int i=1;i<=n;++i) {
		cout<<disb[i]<<' ';
	}cout<<endl;
	bfs(a,disa,visa);
	for(int i=1;i<=n;++i) {
		cout<<disb[i]<<' ';
	}cout<<endl;
	
	if(disb[a] == 0x3f3f3f3f) {
		cout<<"Case #"<<T<<": SAFE"<<'\n';
		return;
	}
	int mx = 0;
	for(int i=1;i<=n;++i) {
		if(disa[i] < disb[i]) {
			if(h[i]) {
				cout<<"Case #"<<T<<": SAFE"<<'\n';
				return;
			} else {
				mx = max(mx, disb[i] * 2);
			}
		}
	}
	cout<<"Case #"<<T<<": "<<mx<<'\n';
	return;
}
void clear(){
	cnt = 0, tim = 0;
	memset(head,0,sizeof(head));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(disa,0x3f,sizeof(disa));
	memset(disb,0x3f,sizeof(disb));
	memset(visa,0,sizeof(visa));
	memset(visb,0,sizeof(visb));
	memset(h,0,sizeof(h));
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>T;
	for(int i=1;i<=T;++i) {
		clear();
		slove(i);
	}
	return 0;
}