#include <bits/stdc++.h>
using namespace std;
const int maxv = 402, maxe = 2 * (5000 + 800);
struct Graph {
  int head[maxv];
  int next[maxe];
  int to[maxe];
  int cf[maxe];
  int w[maxe];
  int k;
  int n;
  Graph(int _n = 0) : n(_n) { clear(); }
  void clear() {
    memset(head, -1, sizeof(head));
    k = 0;
  }
  void adde(int s, int t, int cc, int ww) {
    next[k] = head[s], head[s] = k, to[k] = t, w[k] = ww, cf[k] = cc, k++;
    next[k] = head[t], head[t] = k, to[k] = s, w[k] = -ww, cf[k] = 0, k++;
  }
  int dist[maxv], pr[maxv], maxpush[maxv];
  int st[maxv * maxv];
  bool used[maxv];
  void mincost(int S, int T) {
    while (1) {
      for (int i = 0; i < n; i++)
        dist[i] = ((int)1E9), pr[i] = -1, maxpush[i] = 0, used[i] = 0;
      dist[S] = 0, maxpush[S] = ((int)1E9);
      st[0] = S;
      for (int l = 0, r = 1; l < r; l++) {
        int v = st[l];
        used[v] = 0;
        for (int edge = head[v]; edge != -1; edge = next[edge]) {
          int u = to[edge];
          if (cf[edge] && dist[u] > dist[v] + w[edge]) {
            if (!used[u]) st[r++] = u, used[u] = 1;
            dist[u] = dist[v] + w[edge];
            pr[u] = edge;
            maxpush[u] = min(maxpush[v], cf[edge]);
          }
        }
      }
      if (pr[T] == -1) break;
      for (int v = T; v != S; v = to[pr[v] ^ 1]) {
        cf[pr[v]] -= maxpush[T], cf[pr[v] ^ 1] += maxpush[T];
      }
    }
  }
};
Graph g;
int edges[maxe][2];
int degs[2][maxv];
int ans[maxe];
int main() {
  int n, m, k, t;
  while (scanf("%d%d%d%d", &n, &m, &k, &t) >= 4) {
    memset(degs, 0, sizeof(degs));
    for (int i = 0; i < k; i++)
      for (int j = 0; j < 2; j++)
        scanf("%d", &edges[i][j]), degs[j][--edges[i][j]]++;
    int res = 0;
    for (int i = 0; i < n; i++) res += !!(degs[0][i] % t);
    for (int i = 0; i < m; i++) res += !!(degs[1][i] % t);
    printf("%d\n", res);
    memset(ans, 0, sizeof(ans));
    g.n = n + m + 2;
    for (int parts = t; parts; parts--) {
      g.clear();
      for (int i = 0; i < k; i++)
        if (!ans[i]) g.adde(edges[i][0], n + edges[i][1], 1, 0);
      int S = n + m, T = S + 1;
      for (int i = 0; i < n; i++) {
        g.adde(S, i, degs[0][i] / parts, 0);
        if (degs[0][i] % parts) g.adde(S, i, 1, 1);
      }
      for (int i = 0; i < m; i++) {
        g.adde(i + n, T, degs[1][i] / parts, 0);
        if (degs[1][i] % parts) g.adde(i + n, T, 1, 1);
      }
      g.mincost(S, T);
      for (int i = 0, id = 0; i < k; i++)
        if (!ans[i]) {
          if (!g.cf[id])
            ans[i] = parts, degs[0][edges[i][0]]--, degs[1][edges[i][1]]--;
          id += 2;
        }
    }
    for (int i = 0; i < k; i++) printf("%d%c", ans[i], " \n"[i == k - 1]);
  }
  return 0;
}
