#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void scf(T &x) {
  bool f = 0;
  x = 0;
  char c = getchar();
  while (c != '-' && (c < '0' || c > '9')) c = getchar();
  if (c == '-') f = 1, c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  if (f) x = -x;
  return;
}
template <typename T1, typename T2>
inline void scf(T1 &x, T2 &y) {
  scf(x);
  scf(y);
}
template <typename T1, typename T2, typename T3>
inline void scf(T1 &x, T2 &y, T3 &z) {
  scf(x);
  scf(y);
  scf(z);
}
template <typename T1, typename T2, typename T3, typename T4>
inline void scf(T1 &x, T2 &y, T3 &z, T4 &w) {
  scf(x);
  scf(y);
  scf(z);
  scf(w);
}
template <typename T>
inline bool chkmin(T &x, const T &y) {
  return x > y ? x = y, 1 : 0;
}
template <typename T>
inline bool chkmax(T &x, const T &y) {
  return x < y ? x = y, 1 : 0;
}
const int maxn = 210;
const int maxk = 5010;
const int maxv = maxn * 2;
const int maxe = (maxn * 4 + maxk) * 2;
struct edge {
  int to, cap, cst, next;
  edge() {}
  edge(int N, int T, int C, int CS) : next(N), to(T), cap(C), cst(CS) {}
} e[maxe];
int n, m, k, tot, ans, S, T, e_n;
int x[maxk], y[maxk], col[maxk], cntx[maxn], cnty[maxn];
bool in[maxv];
int dst[maxv], q[maxv * maxv], prevv[maxv], preve[maxv], head[maxv];
void add_edge(int u, int v, int cap, int cst) {
  e[e_n] = edge(head[u], v, cap, cst);
  head[u] = e_n++;
  e[e_n] = edge(head[v], u, 0, -cst);
  head[v] = e_n++;
  return;
}
bool spfa() {
  memset(dst, 0x3f, sizeof dst);
  memset(in, 0, sizeof in);
  int fnt, rar;
  fnt = rar = 0;
  q[rar++] = S;
  dst[S] = 0;
  in[S] = 1;
  while (fnt != rar) {
    int u = q[fnt++];
    in[u] = 0;
    for (int i = head[u]; ~i; i = e[i].next)
      if (e[i].cap && dst[e[i].to] > dst[u] + e[i].cst) {
        dst[e[i].to] = dst[u] + e[i].cst;
        prevv[e[i].to] = u;
        preve[e[i].to] = i;
        if (!in[e[i].to]) q[rar++] = e[i].to, in[e[i].to] = 1;
      }
  }
  return dst[T] < 100000;
}
void mcmf() {
  while (spfa()) {
    int mn = 0x3f;
    for (int u = T; u; u = prevv[u]) chkmin(mn, e[preve[u]].cap);
    for (int u = T; u; u = prevv[u])
      e[preve[u]].cap -= mn, e[preve[u] ^ 1].cap += mn;
  }
  return;
}
int main() {
  scf(n, m, k, tot);
  for (int i = (1); i <= (k); ++i) scf(x[i], y[i]), ++cntx[x[i]], ++cnty[y[i]];
  for (int i = (1); i <= (n); ++i) ans += !!(cntx[i] % tot);
  for (int i = (1); i <= (m); ++i) ans += !!(cnty[i] % tot);
  for (int C = (tot); C >= (1); --C) {
    memset(head, -1, sizeof head);
    S = 0;
    T = n + m + 1;
    e_n = 0;
    for (int i = (1); i <= (k); ++i)
      if (!col[i]) add_edge(x[i], y[i] + n, 1, 0);
    for (int i = (1); i <= (n); ++i) {
      add_edge(S, i, cntx[i] / C, 0);
      if (cntx[i] % C) add_edge(S, i, 1, 1);
    }
    for (int i = (1); i <= (m); ++i) {
      add_edge(i + n, T, cnty[i] / C, 0);
      if (cnty[i] % C) add_edge(i + n, T, 1, 1);
    }
    mcmf();
    e_n = 0;
    for (int i = (1); i <= (k); ++i)
      if (!col[i]) {
        if (!e[e_n].cap) col[i] = C, --cntx[x[i]], --cnty[y[i]];
        e_n += 2;
      }
  }
  printf("%d\n", ans);
  for (int i = (1); i <= (k); ++i) printf("%d%c", col[i], i == k ? '\n' : ' ');
  return 0;
}
