#include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 using namespace std;

 #define maxn 10010

 #define llg long long

 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

 llg n,m,sett,father[maxn],pre[maxn],match[maxn],vis[maxn],id[maxn],dl[maxn*],head,tail,ans,T,totn,e;

 llg c[][];

 vector<llg> a[maxn];

 llg find(llg x){if (father[x]!=x) father[x]=find(father[x]); return father[x];}

 llg lca(llg x,llg y)

 {

     sett++;

     while (vis[x]!=sett)

     {

         if (x)

         {

             x=find(x);

             if (vis[x]==sett) return x;

             vis[x]=sett;

             if (match[x]!=) x=find(pre[match[x]]);

             else x=;

         }

             swap(x,y);

     }

     return x;

 }

 void change(llg x,llg y,llg fa)

 {

     llg z;

     while (find(x)!=fa)

     {

         pre[x]=y; z=match[x];

         if (id[z]==) {id[z]=,dl[++tail]=z;}

         if (find(z)==z) father[z]=fa;

         if (find(x)==x) father[x]=fa;

         y=z; x=pre[y];

     }

 }

 bool bfs(llg p)

 {

     llg x,w,v;

     for (llg i=;i<=n;i++) id[i]=-,father[i]=i;

     head=,tail=,dl[]=p; id[p]=;

     do

     {

         x=dl[++head],w=a[x].size();

         for (llg i=;i<w;i++)

         {

             v=a[x][i];

             if (id[v]==-)

             {

                 pre[v]=x;

                 id[v]=;

                 if (!match[v])

                 {

                     llg last,t,now=v;

                     while (now!=)

                     {

                         t=pre[now],last=match[t];

                         match[t]=now; match[now]=t;

                         now=last;// v=t;

                     }//把原lai的匹配和非匹配bian取反

                     return ;

                 }

                 id[match[v]]=,dl[++tail]=match[v];

             }

             else

                 if (id[v]== && find(v)!=find(x))

                 {

                     llg dad=lca(x,v);

                     change(x,v,dad);

                     change(v,x,dad);

                 }

         }

     }while (head!=tail);

     return ;

 }

 void link(llg x,llg y) {a[x].push_back(y),a[y].push_back(x);}

 void init()

 {

     for (llg i=;i<=n;i++) a[i].clear(),vis[i]=match[i]=pre[i]=father[i]=id[i]=dl[i]=;

     //for (llg i=1;i<=n;i++) for (llg j=1;j<=n;j++) c[i][j]=c[j][i]=0;

     scanf("%lld%lld%lld",&n,&m,&e);

     totn=n;

     llg x,y;

     for (llg i=;i<=e;i++)

     {

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

         llg po=m*+x;

         link(po,y*-),link(po,y*-),link(po,y*);

         //a[x].push_back(y),a[y].push_back(x);

     }

     n=n+m*;

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

     {

         link(i*-,i*-),link(i*-,i*),link(i*,i*-);

     }

 }

 void oupt()

 {

     cout<<ans-totn<<endl;

     for (llg i=;i<=totn;i++)

     {

         printf("%lld ",(match[*m+i]-)/+);

     }

     printf("\n");

 }

 int main()

 {

     //yyj("a");

     cin>>T;

     while (T--)

     {

         ans=;

         init();

         for (llg i=n;i>;i--)

             if (!match[i] && bfs(i)) ans++;

         oupt();

     }

     return ;

 }