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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const ll INF = 2001001001;
const ll INF2 = 2e18;
const ll MOD = 1000000007;

#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define pb push_back 
#define pf push_front
#define f first
#define s second
#define mp make_pair
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

const bool testing = 0;
mt19937 rng(63);

// first four are north, west, east ,south
int dir1[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dir2[] = {0, 1, 0, -1, 1, -1, 1, -1};

int main() {
	cin.tie(0) , ios::sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	stringstream ss;

    int n, m, k;
    cin >> n >> m >> k;
    // build given graph
    vector<vi> vec(n+1);
    vector<int> degree(n+1, 0);
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        vec[a].pb(b), vec[b].pb(a);
        degree[a]++, degree[b]++;
    }
    // orient edges in the given graph into a dag
    vector<bool> oriented(n+1, false);
    queue<int> orient;
    vector<vi> dag(n+1);
    vector<int> indegs(n+1, 0);
    for(int i = 1; i <= n; i++){
        if(degree[i] > k) continue;
        orient.push(i);
    }
    while(sz(orient)){
        int curr = orient.front();
        orient.pop();
        if(oriented[curr]) continue;
        oriented[curr] = true;
        for(auto a : vec[curr]){
            if(oriented[a]) continue;
            dag[a].pb(curr);
            indegs[curr]++;
            degree[a]--;
            if(degree[a] <= k){
                orient.push(a);
            }
        }
    }
    // color the dag
    vector<int> coloring(n+1, 0);
    vector<vi> banned_colors(n+1);
    queue<int> q;
    for(int i = 1; i <= n; i++){
        if(indegs[i] == 0) q.push(i);
    }
    while(sz(q)){
        int curr = q.front();
        q.pop();
        vector<int>& banned = banned_colors[curr];
        banned.pb(0), banned.pb(k+2);
        int l = sz(banned);
        sort(all(banned));
        for(int i = 0; i < l-1; i++){
            if(banned[i+1]-banned[i] > 1){
                coloring[curr] = banned[i]+1;
                break;
            }
        }
        for(auto a : dag[curr]){
            indegs[a]--;
            banned_colors[a].pb(coloring[curr]);
            if(indegs[a] == 0) q.push(a);
        }
    }
    for(int i = 1; i <= n; i++){
        cout << coloring[i] << " ";
    }
    cout << "\n";

	cout << ss.str();
	return 0;
}