#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline ll read() {
  ll x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
const ll inf = 0x3f3f3f3f;
int deg[11010], to[11010][210], id[11010][210], col[5010], cur1[210], cur2[210],
    n1, n2, m, k, cnt, ans;
inline void adjust(int x, int c1, int c2) {
  while (x) {
    col[id[x][c1]] = c2;
    swap(to[x][c1], to[x][c2]);
    swap(id[x][c1], id[x][c2]);
    x = to[x][c2];
    swap(c1, c2);
  }
}
int main() {
  n1 = read();
  n2 = read();
  m = read();
  k = read();
  deg[0] = k;
  cnt = 0;
  for (int i = 1; i <= m; i++) {
    int x = read(), y = read(), cx = 0, cy = 0;
    if (deg[cur1[x]] == k) {
      cur1[x] = ++cnt;
      deg[cur1[x]] = 0;
    }
    if (deg[cur2[y]] == k) {
      cur2[y] = ++cnt;
      deg[cur2[y]] = 0;
    }
    ++deg[cur1[x]];
    ++deg[cur2[y]];
    for (int j = 1; j <= k; j++)
      if (!to[cur1[x]][j]) {
        cx = j;
        break;
      }
    if (to[cur2[y]][cx]) {
      for (int j = 1; j <= k; j++)
        if (!to[cur2[y]][j]) {
          cy = j;
          break;
        }
      adjust(cur2[y], cx, cy);
    }
    to[cur1[x]][cx] = cur2[y];
    id[cur1[x]][cx] = i;
    to[cur2[y]][cx] = cur1[x];
    id[cur2[y]][cx] = i;
    col[i] = cx;
  }
  for (int i = 1; i <= cnt; i++)
    if (deg[i] < k) ++ans;
  printf("%d\n", ans);
  for (int i = 1; i <= m; i++) printf("%d ", col[i]);
  putchar('\n');
  return 0;
}
