#include <bits/stdc++.h>
using namespace std;
struct dat {
  int x, rev, f, cap, cost;
  dat(int x = 0, int rev = 0, int f = 0, int cap = 0, int cost = 0)
      : x(x), rev(rev), f(f), cap(cap), cost(cost) {}
};
vector<dat> v[5100];
void add(int s, int t, int ca, int co) {
  int n = v[s].size();
  int m = v[t].size();
  v[s].push_back(dat(t, m, 0, ca, co));
  v[t].push_back(dat(s, n, 0, 0, -co));
}
priority_queue<pair<int, int> > q;
pair<int, int> pa[5100];
int pot[5100], vis[5100], A[5100 * 10], dist[5100], col[5100][5100], a[5100],
    b[5100], deg[5100], deg1[5100], fl[5100];
int mx = 0;
int doit(int de) {
  int mxx = 0;
  for (int i = 0; i <= de; i++) pot[i] = 1e9;
  pot[0] = 0;
  int qt = 0;
  A[qt++] = 0;
  int nodes = de + 1;
  for (int i = 0; i <= de; i++) vis[i] = 0;
  for (int qh = 0; (qh - qt) % nodes != 0; qh++) {
    int u = A[qh % nodes];
    vis[u] = false;
    for (int i = 0; i < (int)v[u].size(); i++) {
      dat e = v[u][i];
      if (e.cap == e.f) continue;
      int vv = e.x;
      int ndist = pot[u] + e.cost;
      if (pot[vv] > ndist) {
        pot[vv] = ndist;
        if (!vis[vv]) {
          vis[vv] = true;
          A[qt++ % nodes] = vv;
        }
      }
    }
  }
  while (1) {
    for (int i = 0; i <= de; i++) fl[de] = 0;
    for (int i = 0; i <= de; i++) dist[i] = 1e9;
    dist[0] = 0;
    while (!q.empty()) q.pop();
    q.push(pair<int, int>(0, 0));
    fl[0] = 1e9;
    while (!q.empty()) {
      pair<int, int> aa = q.top();
      q.pop();
      int x = aa.second;
      if (-aa.first != dist[x]) continue;
      for (int i = 0; i < v[x].size(); i++) {
        dat bb = v[x][i];
        if (bb.f == bb.cap) continue;
        int y = bb.x;
        int xx = dist[x] + bb.cost + pot[x] - pot[y];
        if (dist[y] > xx) {
          dist[y] = xx;
          q.push(pair<int, int>(-dist[y], y));
          pa[y] = pair<int, int>(x, i);
          fl[y] = min(fl[x], bb.cap - bb.f);
        }
      }
    }
    if (!fl[de]) break;
    mxx += fl[de];
    for (int i = 0; i <= de; i++) pot[i] += dist[i];
    int x = de;
    while (1) {
      pair<int, int> aa = pa[x];
      int y = aa.first;
      int id = aa.second;
      v[y][id].f += fl[de];
      v[x][v[y][id].rev].f -= fl[de];
      if (!y) break;
      x = y;
    }
  }
  return mxx;
}
int main() {
  int n, m, K, T;
  scanf("%d%d%d%d", &n, &m, &K, &T);
  for (int i = 1; i <= K; i++) {
    scanf("%d%d", &a[i], &b[i]);
    deg[a[i]]++;
    deg1[b[i]]++;
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) ans += (deg[i] % T) > 0;
  for (int i = 1; i <= m; i++) ans += (deg1[i] % T) > 0;
  printf("%d\n", ans);
  int so = 0;
  int de = m + n + 1;
  mx = 0;
  for (int i = T; i; i--) {
    for (int j = 0; j <= de; j++) v[j].clear();
    for (int j = 1; j <= K; j++)
      if (!col[a[j]][b[j]]) {
        add(a[j], b[j] + n, 1, 0);
      }
    int kt = 0;
    for (int j = 1; j <= n; j++) {
      add(so, j, deg[j] / i, 0);
      kt += deg[j] / i;
      if (deg[j] % i) add(so, j, 1, 1);
    }
    int kt1 = 0;
    for (int j = 1; j <= m; j++) {
      add(j + n, de, deg1[j] / i, 0);
      if (deg1[j] % i) add(j + n, de, 1, 1);
    }
    int mm = doit(de);
    mx += mm;
    for (int j = 1; j <= n; j++) {
      for (int k = 0; k < v[j].size(); k++) {
        dat aa = v[j][k];
        if (aa.x == so) continue;
        if (aa.f == 1) {
          int y = aa.x;
          if (y > n && y <= n + m) {
            col[j][y - n] = i;
            deg[j]--, deg1[y - n]--;
          }
        }
      }
    }
  }
  for (int i = 1; i <= K; i++) printf("%d ", col[a[i]][b[i]]);
  puts("");
}
