#include <bits/stdc++.h>
using namespace std;
const int N = 405, M = (2e4 + 5) * 205, INF = 1e9, mk = 5005;
int n, m, K, t, h[N], e[M], pre[M], nxt[M], co[M], fl[M], tot, X[M], Y[M], calc,
    vis[N], f[N], T, Ans[M], Id[N][N], now[N], dx[N], dy[N], ans;
void Add(int x, int y, int f, int c) {
  e[++tot] = y;
  nxt[tot] = h[x];
  pre[h[x]] = tot;
  fl[tot] = f;
  co[tot] = c;
  h[x] = tot;
}
bool aug(int x) {
  vis[x] = calc;
  if (x == T) return 1;
  for (int i = now[x]; i; i = nxt[i])
    if (fl[i] > 0 && vis[e[i]] < calc && f[x] == f[e[i]] + co[i]) {
      if (aug(e[i])) {
        fl[i]--;
        fl[i ^ 1]++;
        now[x] = i;
        return 1;
      }
    }
  return now[x] = 0;
}
void flow() {
  for (int i = 0; i <= T; i++) now[i] = h[i];
  for (;;) {
    calc++;
    if (!aug(0)) return;
  }
}
bool check() {
  int tmp = INF;
  for (int i = 0; i <= T; i++)
    if (vis[i] == calc) {
      for (int j = h[i]; j; j = nxt[j])
        if (fl[j] > 0 && vis[e[j]] < calc)
          tmp = min(tmp, f[e[j]] + co[j] - f[i]);
    }
  if (tmp == INF) return 0;
  for (int i = 0; i <= T; i++)
    if (vis[i] == calc) f[i] += tmp;
  return 1;
}
int main() {
  scanf("%d%d%d%d", &n, &m, &K, &t);
  for (int i = 1; i <= K; i++) {
    scanf("%d%d", &X[i], &Y[i]);
    Id[X[i]][Y[i]] = i;
    dx[X[i]]++;
    dy[Y[i]]++;
  }
  tot = 1;
  memset(h, 0, sizeof(h));
  T = n + m + 1;
  for (int i = 1; i <= K; i++) {
    Add(X[i], Y[i] + n, 1, 0);
    Add(Y[i] + n, X[i], 0, 0);
  }
  for (int i = 1; i <= n; i++) ans += (dx[i] % t > 0);
  for (int i = 1; i <= m; i++) ans += (dy[i] % t > 0);
  printf("%d\n", ans);
  for (int col = t; col; col--) {
    memset(h, 0, sizeof(h));
    tot = 1;
    for (int i = 1; i <= K; i++)
      if (!Ans[i]) {
        Add(X[i], Y[i] + n, 1, 0);
        Add(Y[i] + n, X[i], 0, 0);
      }
    for (int i = 1; i <= n; i++) {
      Add(0, i, dx[i] / col, 0);
      Add(i, 0, 0, 0);
      if (dx[i] % col) {
        Add(0, i, 1, 1);
        Add(i, 0, 0, -1);
      }
    }
    for (int i = 1; i <= m; i++) {
      Add(i + n, T, dy[i] / col, 0);
      Add(T, i + n, 0, 0);
      if (dy[i] % col) {
        Add(i + n, T, 1, 1);
        Add(T, i + n, 0, -1);
      }
    }
    memset(vis, 0, sizeof(vis));
    calc = 0;
    memset(f, 0, sizeof(f));
    for (flow(); check(); flow())
      ;
    for (int i = 1; i <= n; i++)
      for (int j = h[i]; j; j = nxt[j])
        if (e[j] > n && !fl[j]) {
          dx[i]--;
          dy[e[j] - n]--;
          Ans[Id[i][e[j] - n]] = col;
        }
  }
  for (int i = 1; i < K; i++) printf("%d ", Ans[i]);
  printf("%d\n", Ans[K]);
  return 0;
}
