#include <bits/stdc++.h>
using namespace std;
const int N = 605, X = 90005, M = 200005;
int n, m, p, S, T, nA, nB, cnt, du[N], le[X], ri[X], ans[X];
int tot, lnk[N], son[M], w[M], v[M], nxt[M];
int q[N], dst[N], pre[N];
bool bo[N], vis[N];
int read() {
  int x = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x;
}
void Ifmin(int &x, int y) {
  if (y < x) x = y;
}
void add(int x, int y, int z1, int z2) {
  tot++;
  son[tot] = y;
  w[tot] = z1;
  v[tot] = z2;
  nxt[tot] = lnk[x];
  lnk[x] = tot;
  tot++;
  son[tot] = x;
  w[tot] = 0;
  v[tot] = -z2;
  nxt[tot] = lnk[y];
  lnk[y] = tot;
}
bool spfa() {
  for (int i = (1); i <= (n); i++) bo[i] = vis[i] = 0, dst[i] = 1e9;
  int hed = 0, tal = 1;
  dst[q[1] = S] = 0;
  bo[S] = vis[S] = 1;
  while (hed != tal) {
    int x = q[hed = (hed + 1) % N];
    vis[x] = 0;
    for (int j = lnk[x]; j; j = nxt[j])
      if (w[j] > 0 && dst[x] + v[j] < dst[son[j]]) {
        dst[son[j]] = dst[x] + v[j];
        bo[son[j]] = 1;
        pre[son[j]] = j;
        if (!vis[son[j]]) vis[q[tal = (tal + 1) % N] = son[j]] = 1;
      }
  }
  return bo[T];
}
void getflow() {
  while (spfa()) {
    int mn = 1e9;
    for (int x = T; x != S; x = son[pre[x] ^ 1]) Ifmin(mn, w[pre[x]]);
    for (int x = T; x != S; x = son[pre[x] ^ 1])
      w[pre[x]] -= mn, w[pre[x] ^ 1] += mn;
  }
}
int main() {
  nA = read(), nB = read(), m = read(), p = read();
  for (int i = (1); i <= (m); i++) le[i] = read(), ri[i] = read();
  for (int i = (1); i <= (m); i++) du[le[i]]++, du[nA + ri[i]]++;
  for (int i = (1); i <= (nA + nB); i++)
    if (du[i] % p) cnt++;
  printf("%d\n", cnt);
  for (n = nA + nB, S = ++n, T = ++n; p; p--) {
    tot = 1;
    memset(lnk, 0, sizeof(lnk));
    for (int i = (1); i <= (m); i++)
      if (!ans[i]) add(le[i], nA + ri[i], 1, 0);
    for (int i = (1); i <= (nA); i++) {
      add(S, i, du[i] / p, 0);
      if (du[i] % p) add(S, i, 1, 1);
    }
    for (int i = (nA + 1); i <= (nA + nB); i++) {
      add(i, T, du[i] / p, 0);
      if (du[i] % p) add(i, T, 1, 1);
    }
    getflow();
    int _ = 0;
    for (int i = (1); i <= (m); i++)
      if (!ans[i]) {
        _ += 2;
        if (!w[_]) ans[i] = p, du[le[i]]--, du[nA + ri[i]]--;
      }
  }
  for (int i = (1); i <= (m); i++) printf("%d ", ans[i]);
  puts("");
  return 0;
}
