#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

//#define DEBUG
#ifdef DEBUG
const ll N = 1000;
#endif
#ifndef DEBUG
const ll N = 200100;
#endif
struct point{
	ll pos;
	bool side;
	ll id;
};
bool cmp(point x, point y)
{
	if(x.pos != y.pos) return x.pos < y.pos;
	if(x.side != y.side) return x.side < y.side;
	return x.id < y.id;
}
vector<point> a;
pii seg[N];
ll ans[N];
set<ll> mex;
struct item{
	ll x;
		
};
bool operator<(item x, item y)
{
	if(seg[x.x].second != seg[y.x].second)return seg[x.x].second < seg[y.x].second;
	return x.x < y.x;
}
set<item> buffer;

int main()
{
	#ifdef DEBUG
	freopen("1.txt", "r", stdin);
	#endif
	#ifndef DEBUG
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	#endif
	ll z;
	cin >> z;
	while(z--)
	{
		ll n, k;
		cin >> n >> k;
		mex.clear();
		a.clear();
		for(ll i=1; i<=k; i++)
			mex.insert(i);
		for(ll i=1; i<=n; i++)
		{
			ll l, r;
			cin >> l >> r;
			r--;
			seg[i+1] = {l, r};
			a.push_back({l, 0, i});
			a.push_back({r, 1, i});
		}
		sort(a.begin(), a.end(), cmp);
		memset(ans, 0, sizeof(ll) * (n+5));
		ll coverage = 0, prev = 0;
		for(point &cur: a)
		{
			if(cur.side == 0)
			{
				if(mex.empty())
					buffer.insert({cur.id});
				else
				{
					ans[cur.id] = *(mex.begin());
					mex.erase(mex.begin());
					if(mex.empty())
						prev = cur.pos;
				}
			}
			else
			{
				if(ans[cur.id])
				{
					if(!buffer.empty())
					{
						auto it = buffer.begin();
						ans[it->x] = ans[cur.id];
						buffer.erase(buffer.begin());
					}
					else 
					{
						if(mex.empty()) coverage += cur.pos - prev + 1;
						mex.insert(ans[cur.id]);
					}
				}
				else
				{
					buffer.erase({cur.id});
					ans[cur.id] = 1;
				}
			}
		}
		cout << coverage << '\n';
		cout << ans[1];
		for(ll i=2; i<=n; i++) cout << ' ' << ans[i];
		cout << '\n'; 
	}
	return 0;
}