#include <cstdio> #include <cctype> #include <vector> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 491520+10; const int maxn = 15; struct node{ int s,x; node(int s=0,int x=0):s(s),x(x){} }q[N],act[N]; int vis[1<<maxn][maxn],n,m,s,t,fa[N],dist[N]; //491520 vector<int> G[maxn]; void print_ans(int front_){ if(fa[front_]==-1) return ; print_ans(fa[front_]); printf("%d %d\n",act[front_].s+1,act[front_].x+1); } int bfs(node& S){ memset(vis,0,sizeof(vis)); q[0] = S; dist[0] = 0; fa[0] = -1; int front_=0,rear=1; while(front_ < rear){ node& u = q[front_]; if(u.x == t-1){ printf("%d\n",dist[front_]); print_ans(front_); return 1; } for(int i=0;i<n;i++)if((u.s>>i)&1){ for(int j=0;j<G[i].size();j++)if(!((u.s>>G[i][j])&1)){ node& v = q[rear]; v = u; if(v.x == i) v.x = G[i][j]; v.s&=~(1<<i); v.s|=(1<<G[i][j]); if(!vis[v.s][v.x]){ vis[v.s][v.x] = 1; fa[rear] = front_; act[rear] = node(i,G[i][j]); dist[rear] = dist[front_] + 1; rear++; } } } front_++; } } int main() { int T,kase=1; scanf("%d",&T); while(T--){ scanf("%d %d %d %d",&n,&m,&s,&t); node S; S.s|=(1<<(s-1)); S.x=s-1; for(int i=1;i<=m;i++) { int x; scanf("%d",&x); S.s|=(1<<(x-1)); } for(int i=0;i<n;i++) G[i].clear(); for(int i=1;i<n;i++){ int x,y; scanf("%d %d",&x,&y); G[x-1].push_back(y-1); G[y-1].push_back(x-1); } printf("Case %d: ",kase++); int ans = bfs(S); printf("\n"); } return 0; }