#include <bits/stdc++.h>
using namespace std;
void readi(int &x) {
  int v = 0, f = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = v * 10 + c - '0';
  while (isdigit(c = getchar())) v = v * 10 + c - '0';
  x = v * f;
}
void readll(long long &x) {
  long long v = 0ll, f = 1ll;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = v * 10 + c - '0';
  while (isdigit(c = getchar())) v = v * 10 + c - '0';
  x = v * f;
}
void readc(char &x) {
  char c;
  while ((c = getchar()) == ' ')
    ;
  x = c;
}
void writes(string s) { puts(s.c_str()); }
void writeln() { writes(""); }
void writei(int x) {
  if (!x) putchar('0');
  char a[25];
  int top = 0;
  while (x) {
    a[++top] = (x % 10) + '0';
    x /= 10;
  }
  while (top) {
    putchar(a[top]);
    top--;
  }
}
void writell(long long x) {
  if (!x) putchar('0');
  char a[25];
  int top = 0;
  while (x) {
    a[++top] = (x % 10) + '0';
    x /= 10;
  }
  while (top) {
    putchar(a[top]);
    top--;
  }
}
long long qp(long long x, long long y) {
  if (y == 0) return 1;
  if (y == 1) return x;
  long long z = qp(x, y / 2);
  z = z * z % 1000000007;
  if (y & 1) z = z * x % 1000000007;
  return z;
}
struct eg {
  int x, y, z, dis, re, id;
} e[100005];
vector<int> bi[100005];
int n, m, i, j, x[100005], y[100005], k, t, c[100005], ans, cnt2, dis[100005],
    pre[100005];
vector<int> wyx[100005];
void edg(int x, int y, int z, int dis, int id = 0) {
  cnt2++;
  e[cnt2] = {x, y, z, dis, cnt2 + 1, id};
  bi[x].push_back(cnt2);
  cnt2++;
  e[cnt2] = {y, x, 0, -dis, cnt2 - 1, 0};
  bi[y].push_back(cnt2);
}
int bfs(int s, int t, int &cst) {
  cst = 0;
  queue<int> q;
  q.push(s);
  for (i = 1; i <= n + m + 2; i++) {
    dis[i] = 1 << 30;
    pre[i] = -1;
  }
  dis[s] = 0;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (i = 0; i < bi[x].size(); i++) {
      if (e[bi[x][i]].z && e[bi[x][i]].y != s &&
          dis[e[bi[x][i]].y] > dis[x] + e[bi[x][i]].dis) {
        dis[e[bi[x][i]].y] = dis[x] + e[bi[x][i]].dis;
        pre[e[bi[x][i]].y] = bi[x][i];
        q.push(e[bi[x][i]].y);
      }
    }
  }
  if (pre[t] == -1) return -1;
  int mx = 1 << 30;
  for (i = t; i != s; i = e[pre[i]].x) {
    mx = min(mx, e[pre[i]].z);
  }
  for (i = t; i != s; i = e[pre[i]].x) {
    cst += mx * e[pre[i]].dis;
    e[pre[i]].z -= mx;
    e[e[pre[i]].re].z += mx;
  }
  return mx;
}
int mincostmaxflow(int st, int ed, int &cst) {
  cst = 0;
  int ans = 0, res, res2;
  for (; res = bfs(st, ed, res2) != -1;) ans += res, cst += res2;
  return ans;
}
int main() {
  cin >> n >> m >> k >> t;
  for (i = 1; i <= k; i++) {
    cin >> x[i] >> y[i];
    y[i] += n;
    wyx[x[i]].push_back(y[i]);
    wyx[y[i]].push_back(x[i]);
  }
  for (i = 1; i <= n + m; i++) {
    if (wyx[i].size() % t != 0) ans++;
  }
  cout << ans << endl;
  int cc;
  if ((t) >= 1)
    for (((cc)) = ((t)); ((cc)) >= (1); ((cc))--) {
      cnt2 = 0;
      if (1 <= (n + m + 2))
        for (((i)) = (1); ((i)) <= ((n + m + 2)); ((i))++) bi[i].clear();
      if (1 <= (k))
        for (((i)) = (1); ((i)) <= ((k)); ((i))++) {
          if (c[i]) continue;
          edg(x[i], y[i], 1, 0, i);
        }
      if (1 <= (n))
        for (((i)) = (1); ((i)) <= ((n)); ((i))++) {
          edg(n + m + 1, i, wyx[i].size() / cc, 0);
          if (wyx[i].size() % cc != 0) edg(n + m + 1, i, 1, 1);
        }
      if (n + 1 <= n + m)
        for ((i) = (n + 1); (i) <= (n + m); (i)++) {
          edg(i, n + m + 2, wyx[i].size() / cc, 0);
          if (wyx[i].size() % cc != 0) edg(i, n + m + 2, 1, 1);
        }
      int rubbish;
      mincostmaxflow(n + m + 1, n + m + 2, rubbish);
      if (1 <= (cnt2))
        for (((i)) = (1); ((i)) <= ((cnt2)); ((i))++) {
          if (!e[i].id) continue;
          if (c[e[i].id]) continue;
          if (!e[i].z) {
            c[e[i].id] = cc;
            wyx[x[e[i].id]].pop_back();
            wyx[y[e[i].id]].pop_back();
          }
        }
    }
  for (i = 1; i <= k; i++) cout << c[i] << ' ';
  return 0;
}
