Expert.
Put your skills to the test.

Problem summary

Color a loopless undirected multigraph of maximum degree at most d with k colors so every vertex has at most floor(d/k) incident edges whose other endpoint has the same color.

Constraints

1 ≤ T ≤ 10; 1 ≤ n ≤ 100000; 1 ≤ m ≤ 200000; 1 ≤ k ≤ d ≤ 100; parallel edges allowed.

Worked example

First official test only, with an independently computed valid coloring.

1
3 3 2 2
1 2
2 3
3 1

2 1 1

Solution analysis

1. Maintain count[v][c], the number of edges from v to color c, counting parallel edges separately. Initially put every vertex in color 1. A vertex is bad when its current-color count exceeds floor(d/k).
2. For a bad vertex choose a color with minimum neighbor count. Pigeonhole guarantees this count is at most floor(deg(v)/k), hence at most floor(d/k). Recolor it and update the counts of its neighbors. A queue tracks vertices that might have become bad; recheck the condition when removing an entry.
3. Every recoloring strictly reduces the total number of monochromatic edges, initially at most m, so there are at most m recolorings. In a triangle with k=d=2, recoloring vertex 1 to color 2 leaves the other two in color 1, each with only one monochromatic incident edge.

Why it works

A recolored bad vertex had more than floor(d/k) same-color neighbors and moves to a color having at most that number, so the global monochromatic-edge potential decreases by at least one. Only neighbors can change their status, and every possibly bad neighbor is queued. The finite process ends with no bad vertex, which is exactly the requested condition.

Watch out. The bound uses d/k rounded down, including when the actual degree is smaller. Count multiedges with multiplicity.

An independently written complete program with standard headers.

// Key idea: A recolored bad vertex had more than floor(d/k) same-color neighbors and moves to a color
// having at most that number, so the global monochromatic-edge potential decreases by at least one.
// Only neighbors can change their status, and every possibly bad neighbor is queued.
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tests;
    cin>>tests;
    while(tests--){
        int n,m,d,k;
        cin>>n>>m>>d>>k;
        vector<vector<int>>graph(n);
        for(int i=0;i<m;++i){
            int u,v;
            cin>>u>>v;
            --u;
            --v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        vector<int>color(n),count(n*k),queued(n);
        queue<int>pending;
        int limit=d/k;
        for(int u=0;u<n;++u){
            count[u*k]=static_cast<int>(graph[u].size());
            if(count[u*k]>limit){
                pending.push(u);
                queued[u]=1;
            }
        }
        while(!pending.empty()){
            int u=pending.front();
            pending.pop();
            queued[u]=0;
            if(count[u*k+color[u]]<=limit){
                continue;
            }
            int next=0;
            for(int c=1;c<k;++c){
                if(count[u*k+c]<count[u*k+next]){
                    next=c;
                }
            }
            int old=color[u];
            color[u]=next;
            for(int v:graph[u]){
                --count[v*k+old];
                ++count[v*k+next];
                if(!queued[v]&&count[v*k+color[v]]>limit){
                    queued[v]=1;
                    pending.push(v);
                }
            }
        }
        for(int u=0;u<n;++u){
            cout<<color[u]+1<<(u+1==n?'\n':' ');
        }
    }
}