#include <bits/stdc++.h>
using namespace std;
template <class Z>
inline bool checkmax(Z &a, Z b) {
  if (a == -1 || a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class Z>
inline bool checkmin(Z &a, Z b) {
  if (a == -1 || a > b) {
    a = b;
    return true;
  }
  return false;
}
int ne, nv, s, t;
int size, net[1100];
struct EDGE {
  int v, next;
  int cap;
  int flow;
  int idx;
} edge[1100000];
void init() {
  size = 0;
  memset(net, -1, sizeof(net));
}
void add(int u, int v, int cap, int idx) {
  edge[size].v = v;
  edge[size].cap = cap;
  edge[size].flow = 0;
  edge[size].next = net[u];
  edge[size].idx = idx;
  net[u] = size;
  ++size;
  edge[size].v = u;
  edge[size].cap = 0;
  edge[size].flow = 0;
  edge[size].next = net[v];
  edge[size].idx = idx;
  net[v] = size;
  ++size;
}
int gap[1100];
int dist[1100];
int pre[1100];
int curedge[1100];
int ISAP(int s, int t) {
  int cur_flow, u, temp, neck, i;
  int max_flow;
  memset(gap, 0, sizeof(gap));
  memset(pre, -1, sizeof(pre));
  memset(dist, 0, sizeof(dist));
  for (i = 1; i <= nv; i++) curedge[i] = net[i];
  gap[nv] = nv;
  max_flow = 0;
  u = s;
  while (dist[s] < nv) {
    if (u == t) {
      cur_flow = 99999999;
      for (i = s; i != t; i = edge[curedge[i]].v) {
        if (cur_flow > edge[curedge[i]].cap) {
          neck = i;
          cur_flow = edge[curedge[i]].cap;
        }
      }
      for (i = s; i != t; i = edge[curedge[i]].v) {
        temp = curedge[i];
        edge[temp].cap -= cur_flow;
        edge[temp].flow += cur_flow;
        temp ^= 1;
        edge[temp].cap += cur_flow;
        edge[temp].flow -= cur_flow;
      }
      max_flow += cur_flow;
      u = neck;
    }
    for (i = curedge[u]; i != -1; i = edge[i].next)
      if (edge[i].cap > 0 && dist[u] == dist[edge[i].v] + 1) break;
    if (i != -1) {
      curedge[u] = i;
      pre[edge[i].v] = u;
      u = edge[i].v;
    } else {
      if (0 == --gap[dist[u]]) break;
      curedge[u] = net[u];
      for (temp = nv, i = net[u]; i != -1; i = edge[i].next)
        if (edge[i].cap > 0)
          temp = temp < dist[edge[i].v] ? temp : dist[edge[i].v];
      dist[u] = temp + 1;
      ++gap[dist[u]];
      if (u != s) u = pre[u];
    }
  }
  return max_flow;
}
struct Fight {
  int x, y, idx;
} fight[5100];
int dx[210], dy[210];
int main() {
  int i, j, h;
  int n, m, k, q;
  int a, b, c;
  int ss, tt;
  while (scanf("%d%d%d%d", &n, &m, &k, &q) != EOF) {
    memset(dx, 0, sizeof(dx));
    memset(dy, 0, sizeof(dy));
    for (i = 1; i <= k; i++) {
      scanf("%d%d", &fight[i].x, &fight[i].y);
      fight[i].idx = -1;
      dx[fight[i].x]++;
      dy[fight[i].y]++;
    }
    int ans = 0;
    for (i = 1; i <= n; i++)
      if (dx[i] % q) ans++;
    for (j = 1; j <= m; j++)
      if (dy[j] % q) ans++;
    int res = 0;
    s = n + m + 1;
    t = n + m + 2;
    ss = n + m + 3;
    tt = n + m + 4;
    nv = tt;
    for (i = 1; i <= q; i++) {
      init();
      add(t, s, 99999999, -1);
      for (j = 1; j <= n; j++) {
        a = dx[j] / (q - i + 1);
        b = (dx[j] + q - i) / (q - i + 1);
        add(s, j, b - a, -1);
        add(s, tt, a, -1);
        add(ss, j, a, -1);
      }
      for (j = 1; j <= m; j++) {
        a = dy[j] / (q - i + 1);
        b = (dy[j] + q - i) / (q - i + 1);
        add(j + n, t, b - a, -1);
        add(j + n, tt, a, -1);
        add(ss, t, a, -1);
      }
      for (j = 1; j <= k; j++) {
        if (fight[j].idx == -1) add(fight[j].x, fight[j].y + n, 1, j);
      }
      res += ISAP(ss, tt);
      for (int u = 1; u <= n; u++) {
        for (j = net[u]; j != -1; j = edge[j].next) {
          if (edge[j].idx != -1 && edge[j].cap == 0) {
            fight[edge[j].idx].idx = i;
            dx[u]--;
            dy[edge[j].v - n]--;
          }
        }
      }
    }
    printf("%d\n", ans);
    for (i = 1; i <= k; i++) {
      printf("%d", fight[i].idx);
      if (i == k)
        printf("\n");
      else
        printf(" ");
    }
  }
  return 0;
}
