#include <bits/stdc++.h>
using namespace std;
const int inf = (signed)(~0u >> 1);
typedef class Edge {
 public:
  int ed, nx, r;
  Edge() {}
  Edge(int ed, int nx, int r) : ed(ed), nx(nx), r(r) {}
} Edge;
typedef class MapManager {
 public:
  int* h;
  vector<Edge> E;
  MapManager() {}
  MapManager(int n) {
    h = new int[(n + 1)];
    memset(h, -1, sizeof(int) * (n + 1));
  }
  ~MapManager() {
    delete[] h;
    E.clear();
  }
  void add_edge(int u, int v, int r) {
    E.emplace_back(v, h[u], r);
    h[u] = (signed)E.size() - 1;
  }
  void add_arc(int u, int v, int r) {
    add_edge(u, v, r);
    add_edge(v, u, 0);
  }
  Edge& operator[](int p) { return E[p]; }
} MapManager;
typedef class Network {
 public:
  int S, T;
  MapManager g;
  int *d, *h;
  Network(int S, int T) : S(S), T(T), g(T) {
    d = new int[(T + 1)];
    h = new int[(T + 1)];
  }
  ~Network() {
    delete[] d;
    delete[] h;
  }
  bool bfs() {
    queue<int> Q;
    memset(d, -1, sizeof(int) * (T + 1));
    d[S] = 0;
    Q.push(S);
    while (!Q.empty()) {
      int e = Q.front();
      Q.pop();
      for (int i = g.h[e], eu; ~i; i = g[i].nx) {
        eu = g[i].ed;
        if (!g[i].r || ~d[eu]) continue;
        d[eu] = d[e] + 1;
        Q.push(eu);
      }
    }
    return d[T] != -1;
  }
  int dfs(int p, int mf) {
    if (p == T || !mf) return mf;
    int flow = 0, f;
    for (int &i = h[p], j, e; ~i; (i != -1) && (i = g[i].nx)) {
      e = g[i].ed, j = i;
      if (g[i].r && d[e] == d[p] + 1 && (f = dfs(e, min(mf, g[i].r))) > 0) {
        g[j].r -= f;
        g[j ^ 1].r += f;
        flow += f;
        mf -= f;
        if (!mf) break;
      }
    }
    return flow;
  }
  int dinic() {
    int rt = 0;
    while (bfs()) {
      for (int i = 0; i <= T; i++) h[i] = g.h[i];
      rt += dfs(S, inf);
    }
    return rt;
  }
  void add_edge(int u, int v, int r) { g.add_arc(u, v, r); }
  int cnt_edges() { return g.E.size(); }
} Network;
const int N = 205;
int n, m, t;
int id[N][N];
int deg[2][N];
bool G[N][N];
int ans[5000];
int idx[N][N];
void solve(int k) {
  Network network(n + m + 2, n + m + 3);
  int S = 0, T = n + m + 1, SS = n + m + 2, TT = n + m + 3;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (G[i][j]) {
        id[i][j] = network.cnt_edges();
        network.add_edge(i, j + n, 1);
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    network.add_edge(SS, i, deg[0][i] / k);
    network.add_edge(S, TT, deg[0][i] / k);
    if (deg[0][i] % k) {
      network.add_edge(S, i, 1);
    }
  }
  for (int i = 1; i <= m; i++) {
    network.add_edge(SS, T, deg[1][i] / k);
    network.add_edge(i + n, TT, deg[1][i] / k);
    if (deg[1][i] % k) {
      network.add_edge(i + n, T, 1);
    }
  }
  network.add_edge(T, S, inf);
  network.dinic();
  MapManager& g = network.g;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (G[i][j] && !g[id[i][j]].r) {
        ans[idx[i][j]] = k;
        G[i][j] = false;
        --deg[0][i];
        --deg[1][j];
      }
    }
  }
}
int main() {
  int _;
  scanf("%d%d%d%d", &n, &m, &_, &t);
  for (int i = 1, u, v; i <= _; i++) {
    scanf("%d%d", &u, &v);
    G[u][v] = true;
    idx[u][v] = i;
    ++deg[0][u];
    ++deg[1][v];
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) ans += !!(deg[0][i] % t);
  for (int i = 1; i <= m; i++) ans += !!(deg[1][i] % t);
  while (t) solve(t--);
  printf("%d\n", ans);
  for (int i = 1; i <= _; i++) {
    if (!::ans[i]) ::ans[i] = 1;
    printf("%d ", ::ans[i]);
  }
  return 0;
}
