cc 12 ambidex 2

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;
typedef unsigned long long LL;
#define FOR(k,a,b) for(int k(a); k < (b); ++k)
#define FORD(k,a,b) for(int k(a-1); k >= (b); --k)
#define REP(k,a) for(int k=0; k < (a); ++k)
#define REPD(k,a) for(int k=a-1; k >-1; --k)
#define ABS(a) ((a)>0?(a):-(a))
#define INF 1e9

inline int score(int a, int b)
{
    return min(a,b);
}

inline int finalScore(int round,int N, const vector<int>& used)
{
    int H=0;
    REP(i,used.size())
        if(used[i])
            ++H;
    return round*N-H;
}

int main()
{
#ifdef HOME
    freopen ("in.txt","r",stdin);
    freopen ("out.txt","w",stdout);
#endif
    int T,N,M;
    vector<pair<int,int> > data;
    vector<int> histo, bestused, used, actual;
    vector<vector<int> > used2;
    data.reserve(1001);
    histo.reserve(101);
    used.reserve(1001);
    used2.reserve(101);
    scanf("%d",&T);
    REP(testcase,T)
    {
        scanf("%d %d",&N,&M);
        data.clear();
        data.resize(M);
        histo.clear();
        histo.resize(N);
        used2.clear();
        REP(i,M)
            scanf("%d",&(data[i].first));
        REP(i,M)
            scanf("%d",&(data[i].second));
        REP(i,M)
        {
            ++histo[--data[i].first];
            ++histo[--data[i].second];
        }
        bool found=true;
        used.clear();
        used.resize(M,0);
        bestused.clear();
        int bestscore=0;
        int round=0;
        do
        {
            ++round;
            actual.clear();
            used2.resize(used2.size()+1);
            vector<int>& actused2=used2.back();
            actused2.resize(N,0);
            int best,bestval;
            do
            {
                best=-1,bestval=INF;
                REP(i,M)
                {
                    if(!used[i] && !actused2[data[i].first] && !actused2[data[i].second] && bestval>score(histo[data[i].first],histo[data[i].second]))
                    {
                        best=i;
                        bestval=score(histo[data[i].first],histo[data[i].second]);
                    }
                }
                if(best>-1)
                {
                    used[best]=round;
                    ++actused2[data[best].first];
                    ++actused2[data[best].second];
                    --histo[data[best].first];
                    --histo[data[best].second];
                    actual.push_back(best);
                }
            }while(best!=-1);
            do
            {
                best=-1,bestval=0;
                REP(i,M)
                {
                    if(!used[i] && (!actused2[data[i].first] || !actused2[data[i].second] )&& bestval<score(histo[data[i].first],histo[data[i].second]))
                    {
                        best=i;
                        bestval=score(histo[data[i].first],histo[data[i].second]);
                    }
                }
                if(best!=-1)
                {
                    used[best]=round;
                    ++actused2[data[best].first];
                    ++actused2[data[best].second];
                    --histo[data[best].first];
                    --histo[data[best].second];
                    actual.push_back(best);
                }
            }while(best!=-1);
            //clear unnecessary
            do
            {
                best=-1,bestval=INF;
                REP(i,actual.size())
                {
                    int& actref=actual[i];
                    if(actref>-1 && actused2[data[actref].first]>1 && actused2[data[actref].second]>1 && bestval>score(histo[data[actref].first],histo[data[actref].second]))
                    {
                        best=i;
                        bestval=score(histo[data[actref].first],histo[data[actref].second]);
                    }
                }
                if(best!=-1)
                {
                    int& actref=actual[best];
                    used[actref]=0;
                    ++histo[data[actref].first];
                    ++histo[data[actref].second];
                    --actused2[data[actref].first];
                    --actused2[data[actref].second];
                    actref=-1;
                }
            }while(best!=-1);
            if(histo.end()==find(histo.begin(),histo.end(),0))
                continue;
            else
            {
//              bool changed=true;
//              //while(changed)
//              {
//                  changed=false;
                FOR(rr,1,round+1)
                {
                    vector<int> actualroundedge,remainededge;
                    REP(j,M)
                    {
                        if(used[j]==0)
                        {
                            remainededge.push_back(j);
                        }
                        else if(used[j]==rr)
                        {
                            actualroundedge.push_back(j);
                        }
                    }
                    vector<int>& w=used2[rr-1];
                    REP(i,w.size())
                    if(w[i]>1)
                    {
                        vector<int> A(N,-1),AA(N,-1),B(N,-1),BB(N,-1);
                        int found=-1;
                        deque<pair<int,int> > q;
                        q.push_back(make_pair(i,0));
                        while(q.size())
                        {
                            const pair<int,int> act=q.front();
                            const int& actnode=act.first;
                            q.pop_front();
                            if(act.second%2)
                            {
                                REP(j,remainededge.size())
                                    if(data[remainededge[j]].first==actnode || data[remainededge[j]].second==actnode)
                                    {
                                        int othernode=data[remainededge[j]].first==actnode?data[remainededge[j]].second:data[remainededge[j]].first;
                                        if(B[othernode]==-1)
                                        {
                                            B[othernode]=remainededge[j];
                                            BB[othernode]=actnode;
                                            q.push_back(make_pair(othernode,act.second+1));
                                        }
                                    }
                            }
                            else
                            {
                                REP(j,actualroundedge.size())
                                    if(data[actualroundedge[j]].first==actnode || data[actualroundedge[j]].second==actnode)
                                    {
                                        int othernode=data[actualroundedge[j]].first==actnode?data[actualroundedge[j]].second:data[actualroundedge[j]].first;
                                        if(A[othernode]==-1)
                                        {
                                            A[othernode]=actualroundedge[j];
                                            AA[othernode]=actnode;
                                            q.push_back(make_pair(othernode,act.second+1));
                                            if((othernode==i && w[i]>2) || ( w[i]>1 && w[othernode]>1))
                                            {
                                                found=othernode;
                                                q.clear();
                                                break;
                                            }
                                        }
                                    }
                            }
                        }
                            if(found>-1)
                            {
//                              changed=true;
                                vector<int> newedge,oldedge;
                                oldedge.push_back(A[found]);
                                found=AA[found];
                                for(int kk=0;found!=i;++kk)
                                {
                                    if(kk%2)
                                    {
                                        oldedge.push_back(A[found]);
                                        found=AA[found];
                                    }
                                    else
                                    {
                                        newedge.push_back(B[found]);
                                        found=BB[found];
                                    }
                                }
                                REP(kk,newedge.size())
                                {
                                    int& actref=newedge[kk];
                                    used[actref]=rr;
                                    --histo[data[actref].first];
                                    --histo[data[actref].second];
                                    ++actused2[data[actref].first];
                                    ++actused2[data[actref].second];
                                }
                                REP(kk,oldedge.size())
                                {
                                    int& actref=oldedge[kk];
                                    used[actref]=0;
                                    ++histo[data[actref].first];
                                    ++histo[data[actref].second];
                                    --actused2[data[actref].first];
                                    --actused2[data[actref].second];
                                }
                                break;
                            }
                        }
                }
                break;
            }
                //if(!changed)
//          }
        }while(true);
        //while(histo.end()==find(histo.begin(),histo.end(),0));
        REP(i,M)
            printf("%d ",/*best*/used[i]);
        printf("\n");
    }
    return 0;
}