#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
const int maxn=1e6+5;
class A
{
public:
    int l,r;
}a[maxn];
class B
{
public:
    int num,loc,typ;
    bool operator<(const B &that)const
    {
        if (loc==that.loc)
            return typ<that.typ;
        return loc<that.loc;
    }
};
inline long long input(){
    long long n=0;
    int f=1;
    char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0' && c<='9'){
        n=(n<<3)+(n<<1)+(c^48);
        c=getchar();
    }
    return n*f;
}
int flag[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    t=input();
    while(t--)
    {
        vector<B> v;
        int n,k;
        n=input();
        k=input();
        for (int i=1;i<=n;i++)
        {
            a[i].l=input();
            a[i].r=input();
            v.push_back({i,a[i].l,1});
            v.push_back({i,a[i].r,0});
            flag[i]=0;
        }
        sort(v.begin(),v.end());
        std::priority_queue<int> s;
        set<pair<int,int>> mp;
        for (int i=1;i<=k;i++)
            s.push(i);
        int pre=0,ans=0;
        for (auto i:v)
        {
            if (pre)
                ans+=i.loc-pre;
            if (i.typ)
            {
                if (s.empty())
                {
                    auto it=*mp.begin();
                    if (it.first<a[i.num].r)
                    {
                        mp.erase(mp.begin());
                        mp.insert({a[i.num].r,it.second});
                        flag[i.num]=it.second;
                    }
                    else
                        flag[i.num]=1;
                }
                else
                {
                    auto now=s.top();
                    s.pop();
                    mp.insert({a[i.num].r,now});
                    flag[i.num]=now;
                }
            }
            else
            {
                auto it=mp.find({i.loc,flag[i.num]});
                if (it!=mp.end())
                {
                    mp.erase(it);
                    s.push(flag[i.num]);
                }
            }
            if (s.empty())
                pre = i.loc;
            else
                pre=0;
        }
        cout<<ans<<'\n';
        for (int i=1;i<n;i++)
            cout<<flag[i]<<' ';
        cout<<flag[n]<<'\n';
    }
}