import sys
readline=sys.stdin.readline
from collections import deque

n, m, k = map(int, readline().split())
vec = [[] for _ in range(n+1)]
degree = [0 for _ in range(n+1)]
for i in range (m):
    a, b = map(int, readline().split())
    vec[a].append(b), vec[b].append(a)
    degree[a] += 1; degree[b] += 1
oriented = [False for _ in range(n+1)]
orient = deque()
dag = [[] for _ in range(n+1)]
indegs = [0 for _ in range(n+1)]
for i in range(1, n+1):
    if degree[i] <= k:
        orient.append(i)
while orient:
    curr = orient.popleft()
    if oriented[curr]: continue
    oriented[curr] = True
    for a in vec[curr]:
        if oriented[a]: continue
        dag[a].append(curr)
        indegs[curr] += 1
        degree[a] -= 1
        if degree[a] <= k:
            orient.append(a)
coloring = [0 for _ in range(n+1)]
banned = [[] for _ in range(n+1)]
q = deque()
for i in range(1, n+1):
    if indegs[i] == 0:
        q.append(i)
while q:
    curr = q.popleft()
    banned[curr].append(0), banned[curr].append(k+2)
    banned[curr].sort()
    for i in range(len(banned[curr])-1):
        if banned[curr][i+1] - banned[curr][i] > 1:
            coloring[curr] = banned[curr][i] + 1
            break
    for a in dag[curr]:
        indegs[a] -= 1
        banned[a].append(coloring[curr])
        if indegs[a] == 0:
            q.append(a)
for i in range(1, n+1):
    print(coloring[i], end=" ")
print()