#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <sstream>
#include <complex>
#include <ctime>
#include <cassert>
#include <functional>

using namespace std;

typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> PII;

#define REP(i,s,t) for(int i=(s);i<(t);i++)
#define FILL(x,v) memset(x,v,sizeof(x))
#define MAXN 200005

VI badj[MAXN], adj[MAXN], radj[MAXN];
int label[MAXN];
int main() {
  int n, m, k;
  cin >> n >> m >> k;
  VI deg(n, 0), indeg(n, 0);
  REP(i,0,m) {
    int x, y;
    cin >> x >> y; x--; y--;
    badj[x].push_back(y);
    badj[y].push_back(x);
    deg[x]++; deg[y]++;
  }
  priority_queue<PII, vector<PII>, greater<PII>> pq;
  REP(i,0,n) pq.push({deg[i], i});

  vector<bool> removed(n, false);
  while (pq.size()) {
    PII t = pq.top(); pq.pop();
    int x = t.second;
    if (removed[x] || deg[x] != t.first) continue;
    removed[x] = true;
    for (int y : badj[x]) {
      if (removed[y]) continue;
      deg[y]--;
      pq.push({deg[y], y});
      adj[y].push_back(x);
      radj[x].push_back(y);
      indeg[x]++;
    }
  }

  VI ans(n, 0);
  int L = 0;
  queue<int> q;
  REP(i,0,n) if (indeg[i] == 0) q.push(i);
  while (q.size()) {
    int x = q.front(); q.pop();
    ++L;
    for (int p : radj[x]) label[ans[p]] = L;
    REP(l,1,k+2) if (label[l] != L) {
      ans[x] = l;
      break;
    }
    for (int y : adj[x]) {
      if (--indeg[y] == 0) q.push(y);
    }
  }

  REP(i,0,n-1) cout << ans[i] << " ";
  cout << ans[n-1] << endl;

  return 0;
}