#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x;
  scanf("%d", &x);
  return x;
}
inline void writeln(int x) { printf("%d\n", x); }
inline void write(int x) { printf("%d ", x); }
int col[2][5555][5555];
void dfs(int p, int x, int y, int c0, int c1) {
  int t = col[p ^ 1][y][c0];
  col[p][x][c0] = y;
  col[p ^ 1][y][c0] = x;
  if (!t) {
    col[p ^ 1][y][c1] = 0;
    return;
  }
  dfs(p ^ 1, y, t, c1, c0);
}
const int E = 1e5 + 5;
int n, m, k, s, ans[E];
int sz[2][205], id[2][205];
map<int, int> Id[5555];
int main() {
  n = read(), m = read(), k = read(), s = read();
  if (s == 1) {
    putchar('0'), putchar('\n');
    for (register int i = (1); i <= int(k); ++i) putchar('1'), putchar(' ');
    return 0;
  }
  int nd = 0, mx = 0;
  for (register int i = (1); i <= int(n); ++i) sz[0][i] = s;
  for (register int i = (1); i <= int(m); ++i) sz[1][i] = s;
  for (register int i = (1); i <= int(k); ++i) {
    int x = read(), y = read();
    if (sz[0][x] == s) sz[0][x] = 0, id[0][x] = ++nd;
    sz[0][x]++;
    x = id[0][x];
    if (sz[1][y] == s) sz[1][y] = 0, id[1][y] = ++nd;
    sz[1][y]++;
    y = id[1][y];
    Id[x][y] = i;
    int c0 = 1, c1 = 1;
    for (; col[0][x][c0]; ++c0)
      ;
    for (; col[1][y][c1]; ++c1)
      ;
    mx = max(mx, max(c0, c1));
    if (c0 == c1) {
      col[0][x][c0] = y;
      col[1][y][c0] = x;
    } else
      dfs(0, x, y, c0, c1);
  }
  int mn = 0;
  for (register int i = (1); i <= int(n); ++i) mn += sz[0][i] != s;
  for (register int i = (1); i <= int(m); ++i) mn += sz[1][i] != s;
  writeln(mn);
  for (register int i = (1); i <= int(nd); ++i)
    for (register int j = (1); j <= int(mx); ++j) {
      if (col[0][i][j]) ans[Id[i][col[0][i][j]]] = j;
    }
  for (register int i = (1); i <= int(k); ++i) write(ans[i]), putchar(' ');
  return 0;
}
