#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:100000000")
using namespace std;
const long double pi = acos(-1.0);
const int N = 5555;
const int INF = (int)1e9;
int u[N], v[N], n, m, k, deg[N], st, fin, st2, fin2, t, color[N];
bool used[N];
struct edge {
  int tov, c, num, rev, f;
  edge(int tov, int c, int num, int rev)
      : tov(tov), c(c), num(num), rev(rev), f(0) {}
};
vector<edge> adj[N];
void add_edge(int u, int v, int c, int num) {
  int unum = ((int)(adj[u]).size()), vnum = ((int)(adj[v]).size());
  adj[u].push_back(edge(v, c, num, vnum));
  adj[v].push_back(edge(u, 0, -1, unum));
}
void add_edge(int u, int v, int l, int r, int num) {
  add_edge(st2, v, l, num);
  add_edge(u, fin2, l, num);
  add_edge(u, v, r - l, num);
}
bool dfs(int v) {
  if (v == fin2) return true;
  if (used[v]) return false;
  used[v] = true;
  for (int i = 0; i < ((int)(adj[v]).size()); ++i)
    if ((adj[v][i].c - adj[v][i].f > 0) && dfs(adj[v][i].tov)) {
      adj[v][i].f++;
      adj[adj[v][i].tov][adj[v][i].rev].f--;
      return true;
    }
  return false;
}
int main() {
  scanf("%d%d%d%d", &n, &m, &k, &t);
  st = n + m, fin = n + m + 1, st2 = n + m + 2, fin2 = n + m + 3;
  for (int i = 0; i < k; ++i) {
    scanf("%d%d", &u[i], &v[i]), --u[i], --v[i], v[i] += n;
    deg[u[i]]++, deg[v[i]]++;
    color[i] = -1;
  }
  int sum = 0;
  for (int i = 0; i < n + m; ++i) sum += (deg[i] + t - 1) / t - (deg[i] / t);
  for (int it = 0; it < t; ++it) {
    for (int i = 0; i < n + m + 4; ++i) adj[i].clear();
    for (int i = 0; i < n; ++i)
      add_edge(st, i, deg[i] / (t - it), (deg[i] + (t - it - 1)) / (t - it),
               -1);
    for (int i = n; i < n + m; ++i)
      add_edge(i, fin, deg[i] / (t - it), (deg[i] + (t - it - 1)) / (t - it),
               -1);
    add_edge(fin, st, INF, -1);
    for (int i = 0; i < k; ++i) {
      if (color[i] != -1) continue;
      add_edge(u[i], v[i], 1, i);
    }
    while (true) {
      memset(used, 0, sizeof(used));
      if (!dfs(st2)) break;
    }
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < ((int)(adj[i]).size()); ++j)
        if ((adj[i][j].f == 1) && (adj[i][j].num != -1)) {
          deg[i]--, deg[adj[i][j].tov]--;
          color[adj[i][j].num] = it;
        }
  }
  printf("%d\n", sum);
  for (int i = 0; i < k; ++i) printf("%d%c", color[i] + 1, " \n"[i == k - 1]);
  return 0;
}
