#include <bits/stdc++.h>
inline long long read() {
  long long x = 0;
  char c = getchar(), f = 1;
  for (; c < '0' || '9' < c; c = getchar())
    if (c == '-') f = -1;
  for (; '0' <= c && c <= '9'; c = getchar()) x = x * 10 + c - '0';
  return x * f;
}
inline void write(long long x) {
  static char buf[20];
  int len = 0;
  if (x < 0) putchar('-'), x = -x;
  for (; x; x /= 10) buf[len++] = x % 10 + '0';
  if (!len)
    putchar('0');
  else
    while (len) putchar(buf[--len]);
}
inline void writesp(long long x) {
  write(x);
  putchar(' ');
}
inline void writeln(long long x) {
  write(x);
  putchar('\n');
}
struct edge {
  int from, to, nxt, flow, id;
} e[50 * 10010];
int fir[10010], deg[10010], mark[10010], cur[10010], lev[10010];
int cur1[10010], cur2[10010];
int x[10010], y[10010], col[10010];
int n1, n2, m, k;
int cnt, tot, S, T;
void add_edge(int x, int y, int flow, int id) {
  e[tot].from = x;
  e[tot].to = y;
  e[tot].flow = flow;
  e[tot].id = id;
  e[tot].nxt = fir[x];
  fir[x] = tot++;
  e[tot].from = y;
  e[tot].to = x;
  e[tot].flow = 0;
  e[tot].id = id;
  e[tot].nxt = fir[y];
  fir[y] = tot++;
}
int dfs(int now, int limit) {
  if (now == T) return limit;
  int ret = 0;
  for (int i = cur[now]; ~i; cur[now] = i = e[i].nxt)
    if (e[i].flow && lev[e[i].to] == lev[now] + 1) {
      int tmp = dfs(e[i].to, std::min(e[i].flow, limit));
      ret += tmp;
      limit -= tmp;
      e[i].flow -= tmp;
      e[i ^ 1].flow += tmp;
      if (!limit) return ret;
    }
  return ret;
}
int dinic() {
  static int q[10010];
  int ret = 0;
  while (1) {
    for (int i = 0; i <= T; i++) lev[i] = 0, cur[i] = fir[i];
    int h = 1, t = 1;
    q[1] = S;
    lev[S] = 1;
    while (h <= t) {
      int now = q[h++];
      for (int i = fir[now]; ~i; i = e[i].nxt)
        if (e[i].flow && !lev[e[i].to]) {
          q[++t] = e[i].to;
          lev[e[i].to] = lev[now] + 1;
        }
    }
    if (!lev[T]) break;
    ret += dfs(S, 0x3f3f3f3f);
  }
  return ret;
}
int main() {
  n1 = read();
  n2 = read();
  m = read();
  k = read();
  for (int i = 1; i <= n1; i++) cur1[i] = i, mark[i] = -1;
  for (int i = 1; i <= n2; i++) cur2[i] = i + n1, mark[i + n1] = 1;
  cnt = n1 + n2;
  memset(fir, 255, sizeof(fir));
  tot = 0;
  for (int i = 1; i <= m; i++) {
    int x = read(), y = read();
    if (deg[cur1[x]] == k) cur1[x] = ++cnt, mark[cur1[x]] = -1;
    if (deg[cur2[y]] == k) cur2[y] = ++cnt, mark[cur2[y]] = 1;
    add_edge(cur1[x], cur2[y], 1, i);
    ++deg[cur1[x]];
    ++deg[cur2[y]];
  }
  int ans = 0;
  for (int i = 1; i <= cnt; i++) ans += (deg[i]) && (deg[i] < k);
  writeln(ans);
  int last = 1;
  for (int i = 1; i <= cnt; i++)
    if (mark[i] == -1) {
      while (deg[i] < k) {
        while (mark[last] != 1 || deg[last] == k) {
          ++last;
          if (last > cnt) mark[last] = 1, ++cnt;
        }
        add_edge(i, last, 1, 0);
        ++deg[i];
        ++deg[last];
      }
    }
  last = 1;
  for (int i = 1; i <= cnt; i++)
    if (mark[i] == 1) {
      while (deg[i] < k) {
        while (mark[last] != -1 || deg[last] == k) {
          ++last;
          if (last > cnt) mark[last] = -1, ++cnt;
        }
        add_edge(last, i, 1, 0);
        ++deg[last];
        ++deg[i];
      }
    }
  S = 0;
  T = cnt + 1;
  for (int i = 1; i <= cnt; i++)
    if (mark[i] == -1)
      add_edge(S, i, 1, 0);
    else
      add_edge(i, T, 1, 0);
  for (int i = 1; i <= k; i++) {
    for (int j = fir[S]; ~j; j = e[j].nxt) e[j].flow = 1, e[j ^ 1].flow = 0;
    for (int j = fir[T]; ~j; j = e[j].nxt) e[j].flow = 0, e[j ^ 1].flow = 1;
    dinic();
    for (int j = 0; j < tot; j++)
      if (mark[e[j].from] == -1 && mark[e[j].to] == 1 && e[j ^ 1].flow) {
        col[e[j].id] = i;
        e[j ^ 1].flow = 0;
      }
  }
  for (int i = 1; i <= m; i++) writesp(col[i]);
  putchar('\n');
  return 0;
}
