#include <bits/stdc++.h>
using namespace std;
struct Set{
    priority_queue<int,vector<int>,greater<int>>qu1,qu2;
    int siz=0;
    void flush(){
        while(!qu1.empty()&&!qu2.empty()&&qu1.top()==qu2.top())qu1.pop(),qu2.pop();
    }
    void insert(int x){
        qu1.push(x);siz++;
    }
    void erase(int x){
        qu2.push(x);siz--;
    }
    int size(){
        return siz;
    }
    int top(){
        flush();
        return qu1.top();
    }
};
void solve()
{
    int n,k;cin>>n>>k;
    vector<pair<int,int>>a(n);
    vector<int> id;
    for(int i=0;i<n;i++){
        cin>>a[i].first>>a[i].second;
        id.push_back(a[i].first);
        id.push_back(a[i].second);
    }
    sort(id.begin(),id.end());
    id.resize(unique(id.begin(),id.end())-id.begin());
    auto getid = [&](int x){
        return lower_bound(id.begin(),id.end(),x)-id.begin();
    };
    vector<vector<int>> add(id.size()),del(id.size());
    for(int i=0;i<n;i++){
        a[i].first=getid(a[i].first);
        a[i].second=getid(a[i].second);
        add[a[i].first].push_back(i);
        del[a[i].second].push_back(i);
    }
    vector<int> ans(n,-1);
    vector<int> hav(k+1),seg(n),in(n);
    Set nothav;//color
    Set notcol_seg;//segment
    int segs=0;
    for(int i=1;i<=k;i++)nothav.insert(i);
    auto insert = [&](int col){
        nothav.erase(col);
    };
    auto erase = [&](int col){
        nothav.insert(col);
    };
    int tot_len=0;
    for(int i=0;i<id.size()-1;i++){
        for(auto it:add[i]){
            notcol_seg.insert(it);
        }
        for(auto it:del[i]){
            if(seg[it])seg[it]=0,erase(ans[it]),segs--;
            else notcol_seg.erase(it);
        }
        // cout<<"i="<<i<<" x="<<id[i]<<endl;
        // cout<<"seg :";for(auto it:seg)cout<<it<<" ";;cout<<endl;
        // cout<<"notcol_seg :";for(auto it:notcol_seg)cout<<it<<" ";;cout<<endl;
        if(segs+notcol_seg.size()>=k){
            tot_len+=id[i+1]-id[i];   
            while(segs<k){
                int seg_id=notcol_seg.top();notcol_seg.erase(seg_id);
                int col = nothav.top();
                // cout<<"seg_id = "<<seg_id<<" col="<<col<<endl;
                ans[seg_id]=col;
                insert(col);
                seg[seg_id]=1;
                segs++;
            } 
        }
    }
    for(int i=0;i<n;i++)if(ans[i]==-1)ans[i]=1;
    cout<<tot_len<<"\n";
    for(int i=0;i<n;i++)cout<<ans[i]<<" \n"[i==n-1];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--)solve();
}

/*
2
3 2
1 5
2 4
3 6
4 2
1 4
5 8
3 6
9 10
*/