#include<cmath>

 #include<vector>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 vector<int > g[];

 int len,a[],dep[],pos[][],dp[][],vis[],cnt[];

 void dfs(int u,int fa,int deep)

 {

     a[++len]=u;

     dep[len]=deep+;

     if(!vis[u])

     {

         cnt[u]=len;

         vis[u]=;

     }

     int sz=g[u].size();

     for(int i=; i<sz; i++)

     {

         if(g[u][i]!=fa)

         {

             dfs(g[u][i],u,deep+);

             a[++len]=u;

             dep[len]=deep+;

         }

     }

 }

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--)

     {

         int n,m;

         len=;

         memset(a,,sizeof(a));

         memset(dep,,sizeof(dep));

         memset(pos,,sizeof(pos));

         memset(dp,,sizeof(dp));

         memset(vis,,sizeof(vis));

         memset(cnt,,sizeof(cnt));

         scanf("%d%d",&n,&m);

         for(int i=; i<=n; i++)

         {

             g[i].clear();

         }

         for(int i=; i<=n-; i++)

         {

             int from,to;

             scanf("%d%d",&from,&to);

             g[from].push_back(to);

             g[to].push_back(from);

         }

         dfs(,,);

         printf("%d\n",len);

         for(int i=; i<=len; i++)

         {

             dp[i][]=dep[i];

             pos[i][]=i;

         }

         for(int j=; j<=; j++)

         {

             for(int i=; i<=len; i++)

             {

                 if(i+(<<(j-))>=len)

                 {

                     break;

                 }

                 if(dp[i][j-]>dp[i+(<<(j-))][j-])

                 {

                     dp[i][j]=dp[i+(<<(j-))][j-];

                     pos[i][j]=pos[i+(<<(j-))][j-];

                 }

                 else

                 {

                     dp[i][j]=dp[i][j-];

                     pos[i][j]=pos[i][j-];

                 }

             }

         }

         for(int i=; i<=m; i++)

         {

             int x,y;

             scanf("%d%d",&x,&y);

             int dx=cnt[x];

             int dy=cnt[y];

             if(dx>dy)

             {

                 swap(dx,dy);

                 swap(x,y);

             }

             int k=(int)(log((double)(dy-dx+))/log(2.0));

             int p;

             if(dp[dx][k]>dp[dy-(<<k)+][k])

             {

                 p=pos[dy-(<<k)+][k];

             }

             else

             {

                 p=pos[dx][k];

             }

             printf("%d\n",a[p]);

         }

     }

 }