/**
 *    author:  longvu
 *    created: 12/05/24 00:15:29
**/
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
const int INF = numeric_limits<int>::max();
const int nax = (int)(2010001);
const int mod = 1e9 + 7;

template<class X, class Y>
bool maximize(X& x, const Y y) {
	if (y > x) {x = y; return true;}
	return false;
}
template<class X, class Y>
bool minimize(X& x, const Y y) {
	if (y < x) {x = y; return true;}
	return false;
}

#define NL 2 * si
#define NR 2 * si + 1

struct Segment_tree {
	int seg[4 * nax];
	void build(int si, int sl, int sr) {
		if (sl == sr) {
			seg[si] = 0;
			return;
		}
		int mid = (sl + sr) >> 1;
		build(NL, sl, mid);
		build(NR, mid + 1, sr);
		seg[si] = min(seg[NL], seg[NR]);
	}

	void update(int si, int sl, int sr, int idx, int val) {
		if (sl > idx || sr < idx) {
			return;
		}
		if (sl == sr) {
			seg[si] = val;
			return;
		}
		int mid = (sl + sr) >> 1;
		update(NL, sl, mid, idx, val);
		update(NR, mid + 1, sr, idx, val);
		seg[si] = min(seg[NL], seg[NR]);
	}

	int get(int si, int sl, int sr) {
		if (sl == sr) {
			return sl;
		}
		int mid = (sl + sr) >> 1;
		if (!seg[NL]) {
			return get(NL, sl, mid);
		}
		return get(NR, mid + 1, sr);
	}
};

int L[nax], R[nax], anstr[nax];
vector<int> memo[nax];
Segment_tree IT;
int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int tt;
	cin >> tt;
	while (tt--) {
		int n, k;
		cin >> n >> k;
		vector<int> value = { -INF};
		for (int i = 1; i <= n; ++i) {
			cin >> L[i] >> R[i];
			value.push_back(L[i]);
			value.push_back(R[i]);
		}
		sort(all(value));
		value.resize(unique(all(value)) - value.begin());
		for (int i = 1; i < sz(value); ++i) {
			memo[i].clear();
		}
		for (int i = 1; i <= n; ++i) {
			L[i] = lower_bound(all(value), L[i]) - value.begin();
			R[i] = lower_bound(all(value), R[i]) - value.begin();
			memo[L[i]].push_back(i);
			memo[R[i]].push_back(-i);
		}
		IT.build(1, 1, k + 1);
		for (int i = 1; i <= n; ++i) {
			anstr[i] = -1;
		}
		set<int> cur;
		int ans = 0;
		for (int i = 1; i + 1 < sz(value); ++i) {
			for (auto z : memo[i]) {
				if (z <= -1) {
					if (anstr[-z] == -1) {
						cur.erase(-z);
					} else {
						IT.update(1, 1, k + 1, anstr[-z], 0);
					}
				} else {
					cur.insert(z);
				}
			}
			while (IT.get(1, 1, k + 1) <= k && !cur.empty()) {
				int z = IT.get(1, 1, k + 1);
				anstr[*cur.begin()] = z;
				cur.erase(cur.begin());
				IT.update(1, 1, k + 1, z, 1);
			}
			// cout << value[i] << " " << IT.get(1, 1, k + 1) << '\n';
			if (IT.get(1, 1, k + 1) == k + 1) {
				ans += value[i + 1] - value[i];
			}
		}
		for (int i = 1; i <= n; ++i) {
			if (anstr[i] == -1) {
				anstr[i] = 1;
			}
		}
		cout << ans << '\n';
		for (int i = 1; i <= n; ++i) {
			cout << anstr[i];
			if (i < n) {
				cout << " ";
			}
		}
		cout << '\n';
	}
	return 0;
}