// Arup Guha
// 1/6/2025
// Solution to 2025 SER D1 Problem G: Galaxy Governance

import java.util.*;
import java.io.*;

public class galaxygovernance {
	
	public static int n;
	public static int e;
	public static int k;
	public static HashSet<Integer>[] g;
	
	public static void main(String[] args) throws Exception {

		// Set up graph.
		BufferedReader stdin =  new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tok = new StringTokenizer(stdin.readLine());
		n = Integer.parseInt(tok.nextToken());
		e = Integer.parseInt(tok.nextToken());
		k = Integer.parseInt(tok.nextToken());
		g = new HashSet[n];
		for (int i=0; i<n; i++)
			g[i] = new HashSet<Integer>();
		
		// Add edges.
		for (int i=0; i<e; i++) {
			tok = new StringTokenizer(stdin.readLine());
			int u = Integer.parseInt(tok.nextToken())-1;
			int v = Integer.parseInt(tok.nextToken())-1;
			g[u].add(v);
			g[v].add(u);
		}
		
		// Keeps track of in degree of vertices in my final graph.
		int[] inDeg = new int[n];
		int numAsgn = 0;
		
		// Keeps track of which vertices edges aren't done yet.
		ArrayList<Integer> notdone = new ArrayList<Integer>();
		for (int i=0; i<n; i++) notdone.add(i);
		
		// Go until everything assigned.
		while (notdone.size() > 0) {
		
			ArrayList<Integer> tmp = new ArrayList<Integer>();
			
			// Go through everything not assigned.
			for (int i=0; i<notdone.size(); i++) {
				
				int x = notdone.get(i);
				
				// Safe to put all these edges going into this.
				if (g[x].size() <= k) {
				
					// When I remove them, that means they aren't incoming anymore.
					for (Integer prev : g[x]) {
						g[prev].remove(x);
						numAsgn++;
					}
				}
				
				// not done.
				else
					tmp.add(x);
			}
			
			// Reassign.
			notdone = tmp;
		}
		
		// Flip the edges. Since In g, g[i] = {a,b} means an edge from a->i and b->i...
		int[] indeg = new int[n];
		ArrayList<Integer>[] gRev = new ArrayList[n];
		for (int i=0; i<n; i++)
			gRev[i] = new ArrayList<Integer>();
		for (int i=0; i<n; i++) {
			for (Integer x: g[i]) {
				gRev[x].add(i);
				indeg[i]++;
			}
		}
		
		// Set up topological sort. These are the vertices with in degree 0.
		ArrayDeque<Integer> q = new ArrayDeque<Integer>();
		for (int i=0; i<n; i++)
			if (g[i].size() == 0)
				q.offer(i);
		
		// Put my coloring here.
		int[] coloring = new int[n];
		Arrays.fill(coloring, -1);
		int done = 0;
		
		// Run top sort.
		while (q.size() > 0) {
		
			// Next item to color.
			int cur = q.poll();
			
			// Mark all colors I can't use.
			TreeSet<Integer> used = new TreeSet<Integer>();
			for (Integer x: g[cur])
				used.add(coloring[x]);
			
			// Find the first one that works.
			// This looks nuts but I am just iterating through each edge twice. 
			// Maybe a hash set would have been faster...
			int asgn = 1;
			while (used.contains(asgn)) asgn++;
			coloring[cur] = asgn;
			
			// Update in degrees and add to queue if we're ready to color it.
			for (Integer x: gRev[cur]) {
				indeg[x]--;
				if (indeg[x] == 0) q.offer(x);
			}
		}
		
		// Put together our answer and output.
		StringBuffer sb = new StringBuffer();
		sb.append(""+coloring[0]);
		for (int i=1; i<n; i++)
			sb.append(" "+coloring[i]);
		System.out.println(sb);
	}
}