//Hints:Competitive programming books by Steven & Felix Halim
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz 123456
#define pii pair<int,int>
vector<pii>v[sz];
vector<pii>::iterator it;
int dist1[sz],N; //initializing distance of each node infinity
int dist2[sz];
void dijkstra(int s){
priority_queue<pii, vector<pii>, greater<pii> >pq;
pq.push(make_pair(0,s)); //shorted in non-increasing order w.r.t distance so that the least distance can be pop out first
dist1[s]=0;
while(!pq.empty()){
pii top=pq.top(); pq.pop();
int d=top.first; int u=top.second;
for(it=v[u].begin();it!=v[u].end();++it){
int v=it->first; int weight_u_v=it->second;
if(dist1[u]+weight_u_v<dist1[v]){
dist1[v]=(dist1[u]+weight_u_v);
pq.push(make_pair(dist1[v],v));
}
}
}
}
void ddijkstra(int s){
priority_queue<pii, vector<pii>, greater<pii> >pq;
pq.push(make_pair(0,s)); //shorted in non-increasing order w.r.t distance so that the least distance can be pop out first
dist2[s]=0;
while(!pq.empty()){
pii top=pq.top(); pq.pop();
int d=top.first; int u=top.second;
for(it=v[u].begin();it!=v[u].end();++it){
int v=it->first; int weight_u_v=it->second;
if(dist2[u]+weight_u_v<dist2[v]){
dist2[v]=(dist2[u]+weight_u_v);
pq.push(make_pair(dist2[v],v));
}
}
}
}
int main()
{
int N,E,s,t,i,j,x,y,w,tc,cs=0,d;
scanf("%d",&tc);
while(tc--){
scanf("%d%d",&N,&E);
for(int i=0;i<=N;i++)dist1[i]=inf;
for(int i=0;i<=N;i++)dist2[i]=inf;
for(i=0;i<E;i++){
scanf("%d%d",&x,&y);
w=1;
v[x].push_back(make_pair(y,w));
v[y].push_back(make_pair(x,w));
}
scanf("%d%d",&s,&d);
dijkstra(s);
ddijkstra(d);
//for(i=0;i<N;i++)cout<<dist1[i]<<' ';cout<<endl;
//for(i=0;i<N;i++)cout<<dist2[i]<<' ';cout<<endl;
int mx=-1;
for(i=0;i<N;i++)mx=max(mx,dist1[i]+dist2[i]);
printf("Case %d: %d\n",++cs,mx);
for(int f=0;f<=N;f++)v[f].clear();
}
return 0;
}
Ly9IaW50czpDb21wZXRpdGl2ZSBwcm9ncmFtbWluZyBib29rcyBieSBTdGV2ZW4gJiBGZWxpeCBIYWxpbQojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIGluZiAweDNmM2YzZjNmCiNkZWZpbmUgc3ogMTIzNDU2CiNkZWZpbmUgcGlpIHBhaXI8aW50LGludD4KdmVjdG9yPHBpaT52W3N6XTsKdmVjdG9yPHBpaT46Oml0ZXJhdG9yIGl0OwppbnQgZGlzdDFbc3pdLE47ICAvL2luaXRpYWxpemluZyBkaXN0YW5jZSBvZiBlYWNoIG5vZGUgaW5maW5pdHkKaW50IGRpc3QyW3N6XTsKdm9pZCBkaWprc3RyYShpbnQgcyl7CiAgICBwcmlvcml0eV9xdWV1ZTxwaWksIHZlY3RvcjxwaWk+LCBncmVhdGVyPHBpaT4gPnBxOwogICAgcHEucHVzaChtYWtlX3BhaXIoMCxzKSk7ICAgIC8vc2hvcnRlZCBpbiBub24taW5jcmVhc2luZyBvcmRlciB3LnIudCBkaXN0YW5jZSBzbyB0aGF0IHRoZSBsZWFzdCBkaXN0YW5jZSBjYW4gYmUgcG9wIG91dCBmaXJzdAogICAgZGlzdDFbc109MDsKICAgIHdoaWxlKCFwcS5lbXB0eSgpKXsKICAgICAgICBwaWkgdG9wPXBxLnRvcCgpOyBwcS5wb3AoKTsKICAgICAgICBpbnQgZD10b3AuZmlyc3Q7IGludCB1PXRvcC5zZWNvbmQ7CiAgICAgICAgICAgIGZvcihpdD12W3VdLmJlZ2luKCk7aXQhPXZbdV0uZW5kKCk7KytpdCl7CiAgICAgICAgICAgICAgICBpbnQgdj1pdC0+Zmlyc3Q7IGludCB3ZWlnaHRfdV92PWl0LT5zZWNvbmQ7CiAgICAgICAgICAgICAgICBpZihkaXN0MVt1XSt3ZWlnaHRfdV92PGRpc3QxW3ZdKXsKICAgICAgICAgICAgICAgICAgICBkaXN0MVt2XT0oZGlzdDFbdV0rd2VpZ2h0X3Vfdik7CiAgICAgICAgICAgICAgICAgICAgcHEucHVzaChtYWtlX3BhaXIoZGlzdDFbdl0sdikpOwogICAgICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KfQp2b2lkIGRkaWprc3RyYShpbnQgcyl7CiAgICBwcmlvcml0eV9xdWV1ZTxwaWksIHZlY3RvcjxwaWk+LCBncmVhdGVyPHBpaT4gPnBxOwogICAgcHEucHVzaChtYWtlX3BhaXIoMCxzKSk7ICAgIC8vc2hvcnRlZCBpbiBub24taW5jcmVhc2luZyBvcmRlciB3LnIudCBkaXN0YW5jZSBzbyB0aGF0IHRoZSBsZWFzdCBkaXN0YW5jZSBjYW4gYmUgcG9wIG91dCBmaXJzdAogICAgZGlzdDJbc109MDsKICAgIHdoaWxlKCFwcS5lbXB0eSgpKXsKICAgICAgICBwaWkgdG9wPXBxLnRvcCgpOyBwcS5wb3AoKTsKICAgICAgICBpbnQgZD10b3AuZmlyc3Q7IGludCB1PXRvcC5zZWNvbmQ7CiAgICAgICAgICAgIGZvcihpdD12W3VdLmJlZ2luKCk7aXQhPXZbdV0uZW5kKCk7KytpdCl7CiAgICAgICAgICAgICAgICBpbnQgdj1pdC0+Zmlyc3Q7IGludCB3ZWlnaHRfdV92PWl0LT5zZWNvbmQ7CiAgICAgICAgICAgICAgICBpZihkaXN0Mlt1XSt3ZWlnaHRfdV92PGRpc3QyW3ZdKXsKICAgICAgICAgICAgICAgICAgICBkaXN0Mlt2XT0oZGlzdDJbdV0rd2VpZ2h0X3Vfdik7CiAgICAgICAgICAgICAgICAgICAgcHEucHVzaChtYWtlX3BhaXIoZGlzdDJbdl0sdikpOwogICAgICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KfQppbnQgbWFpbigpCnsKICAgIGludCBOLEUscyx0LGksaix4LHksdyx0Yyxjcz0wLGQ7CiAgICBzY2FuZigiJWQiLCZ0Yyk7CiAgICB3aGlsZSh0Yy0tKXsKICAgIHNjYW5mKCIlZCVkIiwmTiwmRSk7CiAgICBmb3IoaW50IGk9MDtpPD1OO2krKylkaXN0MVtpXT1pbmY7CiAgICBmb3IoaW50IGk9MDtpPD1OO2krKylkaXN0MltpXT1pbmY7CiAgICBmb3IoaT0wO2k8RTtpKyspewogICAgICAgIHNjYW5mKCIlZCVkIiwmeCwmeSk7CiAgICAgICAgdz0xOwogICAgICAgIHZbeF0ucHVzaF9iYWNrKG1ha2VfcGFpcih5LHcpKTsKICAgICAgICB2W3ldLnB1c2hfYmFjayhtYWtlX3BhaXIoeCx3KSk7CiAgICB9CiAgICBzY2FuZigiJWQlZCIsJnMsJmQpOwogICAgZGlqa3N0cmEocyk7CiAgICBkZGlqa3N0cmEoZCk7CiAgICAvL2ZvcihpPTA7aTxOO2krKyljb3V0PDxkaXN0MVtpXTw8JyAnO2NvdXQ8PGVuZGw7CiAgICAvL2ZvcihpPTA7aTxOO2krKyljb3V0PDxkaXN0MltpXTw8JyAnO2NvdXQ8PGVuZGw7CiAgICBpbnQgbXg9LTE7CiAgICBmb3IoaT0wO2k8TjtpKyspbXg9bWF4KG14LGRpc3QxW2ldK2Rpc3QyW2ldKTsKICAgIHByaW50ZigiQ2FzZSAlZDogJWRcbiIsKytjcyxteCk7CiAgICBmb3IoaW50IGY9MDtmPD1OO2YrKyl2W2ZdLmNsZWFyKCk7CiAgICB9CiAgICByZXR1cm4gMDsKfQoKCgo=