package main

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

type Edge struct {
	to  int
	rev int
	cap int
}

type Dinic struct {
	g     [][]Edge
	level []int
	it    []int
}

func NewDinic(n int) *Dinic {
	return &Dinic{
		g:     make([][]Edge, n),
		level: make([]int, n),
		it:    make([]int, n),
	}
}

func (d *Dinic) AddEdge(fr, to, cap int) int {
	idx := len(d.g[fr])
	d.g[fr] = append(d.g[fr], Edge{to: to, rev: len(d.g[to]), cap: cap})
	d.g[to] = append(d.g[to], Edge{to: fr, rev: idx, cap: 0})
	return idx
}

func (d *Dinic) bfs(s, t int) bool {
	for i := range d.level {
		d.level[i] = -1
	}
	q := make([]int, 0, len(d.g))
	d.level[s] = 0
	q = append(q, s)
	for h := 0; h < len(q); h++ {
		v := q[h]
		for _, e := range d.g[v] {
			if e.cap > 0 && d.level[e.to] < 0 {
				d.level[e.to] = d.level[v] + 1
				q = append(q, e.to)
			}
		}
	}
	return d.level[t] >= 0
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func (d *Dinic) dfs(v, t, f int) int {
	if v == t {
		return f
	}
	for ; d.it[v] < len(d.g[v]); d.it[v]++ {
		i := d.it[v]
		e := &d.g[v][i]
		if e.cap > 0 && d.level[v] < d.level[e.to] {
			ret := d.dfs(e.to, t, min(f, e.cap))
			if ret > 0 {
				e.cap -= ret
				re := &d.g[e.to][e.rev]
				re.cap += ret
				return ret
			}
		}
	}
	return 0
}

func (d *Dinic) MaxFlow(s, t int) int {
	flow := 0
	const inf = int(1 << 60)
	for d.bfs(s, t) {
		for i := range d.it {
			d.it[i] = 0
		}
		for {
			f := d.dfs(s, t, inf)
			if f == 0 {
				break
			}
			flow += f
		}
	}
	return flow
}

func main() {
	in := bufio.NewReaderSize(os.Stdin, 1<<20)
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	var n, m, k, t int
	fmt.Fscan(in, &n, &m, &k, &t)

	u := make([]int, k)
	v := make([]int, k)
	degL0 := make([]int, n)
	degR0 := make([]int, m)

	for i := 0; i < k; i++ {
		var x, y int
		fmt.Fscan(in, &x, &y)
		x--
		y--
		u[i] = x
		v[i] = y
		degL0[x]++
		degR0[y]++
	}

	ans := make([]int, k)
	active := make([]bool, k)
	for i := 0; i < k; i++ {
		active[i] = true
	}

	for c := 1; c < t; c++ {
		r := t - c + 1

		degL := make([]int, n)
		degR := make([]int, m)
		ecnt := 0
		for i := 0; i < k; i++ {
			if active[i] {
				degL[u[i]]++
				degR[v[i]]++
				ecnt++
			}
		}
		if ecnt == 0 {
			break
		}

		S := 0
		T := n + m + 1
		SS := n + m + 2
		TT := n + m + 3
		N := n + m + 4

		d := NewDinic(N)
		demand := make([]int, N)

		addBounded := func(fr, to, low, high int) int {
			demand[fr] -= low
			demand[to] += low
			if high > low {
				return d.AddEdge(fr, to, high-low)
			}
			return -1
		}

		refFrom := make([]int, k)
		refIdx := make([]int, k)
		for i := 0; i < k; i++ {
			refIdx[i] = -1
		}

		for i := 0; i < n; i++ {
			low := degL[i] / r
			high := (degL[i] + r - 1) / r
			addBounded(S, 1+i, low, high)
		}

		for i := 0; i < k; i++ {
			if !active[i] {
				continue
			}
			from := 1 + u[i]
			to := 1 + n + v[i]
			refFrom[i] = from
			refIdx[i] = addBounded(from, to, 0, 1)
		}

		for i := 0; i < m; i++ {
			low := degR[i] / r
			high := (degR[i] + r - 1) / r
			addBounded(1+n+i, T, low, high)
		}

		lowE := ecnt / r
		highE := (ecnt + r - 1) / r
		addBounded(T, S, lowE, highE)

		need := 0
		for i := 0; i < N; i++ {
			if demand[i] > 0 {
				d.AddEdge(SS, i, demand[i])
				need += demand[i]
			} else if demand[i] < 0 {
				d.AddEdge(i, TT, -demand[i])
			}
		}

		if d.MaxFlow(SS, TT) != need {
			return
		}

		for i := 0; i < k; i++ {
			if active[i] && d.g[refFrom[i]][refIdx[i]].cap == 0 {
				active[i] = false
				ans[i] = c
			}
		}
	}

	for i := 0; i < k; i++ {
		if active[i] {
			ans[i] = t
		}
	}

	uneven := 0
	for i := 0; i < n; i++ {
		if degL0[i]%t != 0 {
			uneven = 1
			break
		}
	}
	if uneven == 0 {
		for i := 0; i < m; i++ {
			if degR0[i]%t != 0 {
				uneven = 1
				break
			}
		}
	}

	fmt.Fprintln(out, uneven)
	for i := 0; i < k; i++ {
		if i > 0 {
			fmt.Fprint(out, " ")
		}
		fmt.Fprint(out, ans[i])
	}
	fmt.Fprintln(out)
}