package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReaderSize(os.Stdin, 1<<20)

	var n, m, k int
	if _, err := fmt.Fscan(in, &n, &m, &k); err != nil {
		return
	}

	for i := 0; i < n; i++ {
		var x int
		fmt.Fscan(in, &x)
	}

	a := make([]int, m)
	b := make([]int, m)
	outLists := make([][]int, n)
	inLists := make([][]int, n)

	for i := 0; i < m; i++ {
		fmt.Fscan(in, &a[i], &b[i])
		a[i]--
		b[i]--
		outLists[a[i]] = append(outLists[a[i]], i)
		inLists[b[i]] = append(inLists[b[i]], i)
	}

	leftOf := make([]int, m)
	rightOf := make([]int, m)

	L := 0
	for v := 0; v < n; v++ {
		list := outLists[v]
		for i := 0; i < len(list); i += k {
			id := L
			L++
			end := i + k
			if end > len(list) {
				end = len(list)
			}
			for _, e := range list[i:end] {
				leftOf[e] = id
			}
		}
	}

	R := 0
	for v := 0; v < n; v++ {
		list := inLists[v]
		for i := 0; i < len(list); i += k {
			id := R
			R++
			end := i + k
			if end > len(list) {
				end = len(list)
			}
			for _, e := range list[i:end] {
				rightOf[e] = id
			}
		}
	}

	leftInc := make([][]int, L)
	for i := 0; i < L; i++ {
		row := make([]int, k+1)
		for j := range row {
			row[j] = -1
		}
		leftInc[i] = row
	}

	rightInc := make([][]int, R)
	for i := 0; i < R; i++ {
		row := make([]int, k+1)
		for j := range row {
			row[j] = -1
		}
		rightInc[i] = row
	}

	color := make([]int, m)

	assign := func(e, c int) {
		color[e] = c
		leftInc[leftOf[e]][c] = e
		rightInc[rightOf[e]][c] = e
	}

	for e := 0; e < m; e++ {
		u := leftOf[e]
		v := rightOf[e]

		common := 0
		for c := 1; c <= k; c++ {
			if leftInc[u][c] == -1 && rightInc[v][c] == -1 {
				common = c
				break
			}
		}
		if common != 0 {
			assign(e, common)
			continue
		}

		afree := 0
		for c := 1; c <= k; c++ {
			if leftInc[u][c] == -1 {
				afree = c
				break
			}
		}

		bfree := 0
		for c := 1; c <= k; c++ {
			if rightInc[v][c] == -1 {
				bfree = c
				break
			}
		}

		path := make([]int, 0)
		side := 0
		cur := u
		want := bfree

		for {
			ee := -1
			if side == 0 {
				ee = leftInc[cur][want]
			} else {
				ee = rightInc[cur][want]
			}
			if ee == -1 {
				break
			}
			path = append(path, ee)
			if side == 0 {
				cur = rightOf[ee]
				side = 1
			} else {
				cur = leftOf[ee]
				side = 0
			}
			if want == afree {
				want = bfree
			} else {
				want = afree
			}
		}

		for _, ee := range path {
			c := color[ee]
			leftInc[leftOf[ee]][c] = -1
			rightInc[rightOf[ee]][c] = -1
		}

		for _, ee := range path {
			if color[ee] == afree {
				color[ee] = bfree
			} else {
				color[ee] = afree
			}
			c := color[ee]
			leftInc[leftOf[ee]][c] = ee
			rightInc[rightOf[ee]][c] = ee
		}

		assign(e, bfree)
	}

	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	for i := 0; i < m; i++ {
		fmt.Fprintln(out, color[i])
	}
}