#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
struct qj{
	int l,r,id;
};
qj p[200005];
bool cmp(qj a,qj b)
{
	return a.l<b.l;
}
const int inf=1e9+5;
int answ[200005];
inline void solve()
{
	int n,k;
	cin>>n>>k;
	priority_queue<pair<int,int>> pq;
	for(int i=1;i<=n;i++) cin>>p[i].l,cin>>p[i].r,p[i].id=i;
	for(int i=1;i<=k;i++) pq.push(mp(0,i));
	sort(p+1,p+n+1,cmp);
	int ans=0;
	int lastr=0;
	for(int i=1;i<=n;i++)
	{
		int L=p[i].l,R=p[i].r,id=p[i].id;
		answ[id] = pq.top().second;
		int lsr=-pq.top().first;
		if(lsr < R)
		{
			pq.pop();
			pq.push(mp(-R,answ[id]));
		}
		
		int r0=-pq.top().first;
		if(r0 >= L)
		{
			ans+=r0-max(lastr,L);
			lastr=r0;
		}
	}
	cout<<ans<<endl;
	for(int i=1;i<n;i++) cout<<answ[i]<<" ";
	cout<<answ[n]<<endl;
}
int main()
{
	ios::sync_with_stdio(0);
	int T;
	cin>>T;
	while(T--) solve();
}