#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
using pi = pair <int, int> ;

cs int N = 4e5 + 5; 

int n, k, T; 
struct seg {
    int l, r, c;
    bool operator < (cs seg & x) cs {
        return l < x.l; 
    }
} a[N];

int ans[N];
int b[N], m; 

void Main() {
    cin >> n >> k; 
    m = 0; 
    k = min(n + 1, k);
    for(int i = 1; i <= n; i++) {
        cin >> a[i].l >> a[i].r; 
        a[i].c = i; 
        b[++ m] = a[i].l;
        b[++ m] = a[i].r;
    }
    sort(b + 1, b + m + 1);
    m = unique(b + 1, b + m + 1) - b - 1;
    sort(a + 1, a + n + 1);
    priority_queue <pi> q; 
    for(int i = 1; i <= k; i++) q.push({0, i});
    for(int i = 1; i <= n; i++) {
        auto [l, r, c] = a[i];
        auto [k, color] = q.top();
        q.pop();
        k = max(-k, r);
        ans[c] = color;
        q.push({-k, color}); 
    }
    vector <int> d(m + 1);
    static vector <int> e[N];
    for(int i = 1; i <= n; i++) {
        a[i].l = lower_bound(b + 1, b + m + 1, a[i].l) - b;
        a[i].r = lower_bound(b + 1, b + m + 1, a[i].r) - b; 
        ++ d[a[i].l];
        -- d[a[i].r];
        // e[a[i].l].pb(ans[a[i].c]);
        // e[a[i].r].pb(-ans[a[i].c]);
    }
    int sum = 0; 
    // vector <int> bin(k + 1);
    int FLAG = 0; 
    for(int i = 1; i < m; i++) {
        // for(auto x : e[i]) {
        //     if(x > 0) FLAG += bin[x] == 0, bin[x] ++; 
        //     else bin[- x] --, FLAG -= bin[-x] == 0; 
        // }
        d[i] += d[i - 1];
        if(d[i] >= k) sum += b[i + 1] - b[i];
    }
    cout << sum << '\n';
    for(int i = 1; i <= n; i++) {
        cout << ans[i];
        if(i < n) cout << ' ';
        else cout << '\n'; 
    }
    for(int i = 0; i <= n * 2; i++) ans[i] = 0, b[i] = 0;
}

int main() {
    #ifdef zqj
    freopen("1.in","r",stdin);
    #endif
    ios :: sync_with_stdio(0), cin.tie(0);
    cin >> T; 
    while(T--) {
        Main();
    }
    return 0; 
}