#include <bits/stdc++.h>
using namespace std;

const int N = 100, TOT = N+N+5;

int n, m, c, k;

int dfs(int i, int lim, int term, vector<int> *level, int *point, int *dist, map<int, int> *con){
	if (i == term){
		return lim;
	}
	if (point[i] == (int)level[i].size()){
		return 0;
	}
	int sum = 0;
	for (; point[i] < (int)level[i].size(); point[i] ++){
		while (con[i][level[i][point[i]]]){
			int v = dfs(level[i][point[i]], min(lim-sum, con[i][level[i][point[i]]]), term, level, point, dist, con);
			sum += v;
			con[i][level[i][point[i]]] -= v;
			con[level[i][point[i]]][i] += v;
			if (v == 0){
				break;
			}
			if (sum == lim){
				return lim;
			}
		}
	}
	return sum;
}

int dinuc(map<int, int> *con, int tot, int src, int term){
	vector<int> level[tot];
	int point[tot], dist[tot];

	memset(point, 0, sizeof(int) * tot);
	memset(dist, -1, sizeof(int) * tot);
	for (int x = 0; x < tot; x ++){
		level[x].clear();
	}

	queue<array<int, 2>> que;
	que.push({src, 0});
	while (!que.empty()){
		array<int, 2> cur = que.front();
		que.pop();
		if (dist[cur[0]] != -1){
			continue;
		}
		dist[cur[0]] = cur[1];
		if (cur[0] == term){
			break;
		}
		for (pair<int, int> e: con[cur[0]]){
			if (e.second > 0){
				que.push({e.first, cur[1]+1});
			}
		}
	}
	for (int x = 0; x < tot; x ++){
		for (pair<int, int> e: con[x]){
			if (e.second > 0 && dist[e.first] > dist[x]){
				level[x].push_back(e.first);
			}
		}
	}
	return dfs(src, 1e9, term, level, point, dist, con);
}

void reduce(set<array<int, 3>> &a, set<array<int, 3>> &b, int tot){
	if (a.size() > b.size()){
		swap(a, b);
	}

	if ((int)a.size() == k || (int)b.size() == k){
		return;
	}

	int mat[tot];
	int rev[tot];
	memset(mat, -1, sizeof(mat));
	memset(rev, -1, sizeof(mat));
	for (array<int, 3> e: a){
		mat[e[0]] = e[1];
		rev[e[1]] = e[0];
	}
	for (array<int, 3> e: b){
		mat[e[1]] = e[0];
		rev[e[0]] = e[1];
	}

	int i = 0;
	while (!((int)a.size() == k || (int)b.size() == k)){
		if (rev[i] == -1){
			int nex = i;
			while (mat[nex] != -1){
				nex = mat[nex];
				if (nex == i){
					break;
				}
			}
			if (nex != i && nex < n){
				while (nex != -1){
					array<int, 3> e1 = {min(mat[nex], nex), max(mat[nex], nex), 0};
					array<int, 3> e2 = {min(rev[nex], nex), max(rev[nex], nex), 0};
					if (nex < n){
						if (mat[nex] != -1) {
							auto it = a.lower_bound(e1);
							assert((*it)[0] == e1[0] && (*it)[1] == e1[1]);
							e1 = *it;
							a.erase(e1);
							assert(b.insert(e1).second);
						}
						if (rev[nex] != -1) {
							auto it = b.lower_bound(e2);
							assert((*it)[0] == e2[0] && (*it)[1] == e2[1]);
							e2 = *it;
							b.erase(e2);
							assert(a.insert(e2).second);
						}
					}else {
						if (mat[nex] != -1) {
							auto it = b.lower_bound(e1);
							assert((*it)[0] == e1[0] && (*it)[1] == e1[1]);
							e1 = *it;
							b.erase(e1);
							assert(a.insert(e1).second);
						}
						if (rev[nex] != -1) {
							auto it = a.lower_bound(e2);
							assert((*it)[0] == e2[0] && (*it)[1] == e2[1]);
							e2 = *it;
							a.erase(e2);
							assert(b.insert(e2).second);
						}
					}
					swap(mat[nex], rev[nex]);
					nex = mat[nex];
				}
			}
		}
		i ++;
		if (i == n){
			break;
		}
	}
}

int main(){
	scanf("%d %d %d %d", &n, &m, &c, &k);
	multiset<array<int, 3>> sig;
	multiset<array<int, 3>> truEdges;
	int lim = 1e9;
	int tot;
	int src, term;
	tot = n+m+2;
	src = n+m;
	term = n+m+1;
	int deg[tot];
	memset(deg, 0, sizeof(deg));
	int res = 1;
	{
		map<int, int> con[tot];
		int flow = 0;

		for (int x = 0; x < c; x ++){
			int a, b;
			scanf("%d %d", &a, &b);
			a --, b --;
			truEdges.insert({a, b+n, x});
			con[a][n+b] += 1;
			deg[a] ++;
			deg[n+b] ++;
		}
		for (int x = 0; x < n; x ++){
			lim = min(lim, deg[x]);
		}

		for (; res <= lim; res ++){
			for (int x = 0; x < n; x ++){
				con[src][x] += 1;
			}
			for (int x = 0; x < m; x ++){
				con[n+x][term] += 1;
			}
			while (true){
				int v = dinuc(con, tot, src, term);
				flow += v;

				if (v == 0) break;
			}
			if (flow < res*k){
				break;
			}
		}
		sig.clear();
		memset(deg, 0, sizeof(deg));
		for (array<int, 3> e: truEdges){
			if (con[e[1]][e[0]]){
				sig.insert(e);
				deg[e[0]] ++;
				deg[e[1]] ++;
				con[e[1]][e[0]] --;
			}
		}
		res --;
		printf("%d\n", res);
	}
	set<array<int, 3>> match[lim];
	for (int K = res; K > 0; K --){
		map<int, int> con1[tot];
		map<int, int> con2[tot];

		for (int x = 0; x < n; x ++){
			if (deg[x] == K) con1[src][x] = 1;
			con2[x][term] = 1;
		}
		for (int x = 0; x < m; x ++){
			con1[n+x][term] = 1;
			if (deg[n+x] == K) con2[src][n+x] = 1;
		}

		for (array<int, 3> e: sig){
			con1[e[0]][e[1]] ++;
			con2[e[1]][e[0]] ++;
		}

		int flow1 = 0, flow2 = 0;
		while (true){
			int v = dinuc(con1, tot, src, term);
			flow1 += v;

			if (v == 0) break;
		}
		while (true){
			int v = dinuc(con2, tot, src, term);
			flow2 += v;

			if (v == 0) break;
		}

		int mat[tot];
		int rev[tot];
		memset(mat, -1, sizeof(mat));
		memset(rev, -1, sizeof(mat));
		for (array<int, 3> e: sig){
			for (int x = 0; x < con1[e[1]][e[0]]; x ++){
				assert(deg[e[0]] == K);
				mat[e[0]] = e[1];
				rev[e[1]] = e[0];
			}
			for (int x = 0; x < con2[e[0]][e[1]]; x ++){
				assert(deg[e[1]] == K);
				mat[e[1]] = e[0];
				rev[e[0]] = e[1];
			}
		}
		for (int x = 0; x < n; x ++){
			if (deg[x] == K){
				assert(mat[x] != -1);
				if (rev[x] != -1){
					int i = rev[x];
					while (rev[i] != -1){
						i = rev[i];
						if (i == x){
							mat[rev[x]] = -1;
							break;
						}
					}
					while (i != -1 && mat[i] == -1){
						int nex = mat[mat[i]];
						mat[mat[i]] = i;
						i = nex;
					}
				}
			}
		}
		for (int x = 0; x < tot; x ++){
			if (deg[x] == K){
				array<int, 2> e = {min(x, mat[x]), max(x, mat[x])};
				auto it = truEdges.lower_bound({e[0], e[1], 0});
				assert(it != truEdges.end());
				array<int, 3> e2 = *it;
				match[K-1].insert(e2);
				truEdges.erase(e2);
				sig.erase(e2);
				deg[x] --;
				deg[mat[x]] --;
			}
		}
	}
	set<int> gr, le;
	for (int x = 0; x < res; x ++){
		if ((int)match[x].size() > k){
			gr.insert(x);
		}else if ((int)match[x].size() < k){
			le.insert(x);
		}
	}
	swap(gr, le);
	while (!gr.empty()){
		vector<int> rem2;
		for (int x: gr){
			vector<int> rem;
			for (int y: le){
				reduce(match[y], match[x], tot);
				if ((int)match[y].size() == k){
					rem.push_back(y);
				}
				if ((int)match[x].size() == k){
					rem2.push_back(x);
					break;
				}
			}
			for (int x: rem){
				le.erase(x);
			}
			if ((int)match[x].size() == k){
				rem2.push_back(x);
			}
		}
		for (int x: rem2){
			gr.erase(x);
		}
	}
	for (int x = 0; x < res; x ++){
		int setV[n];
		memset(setV, -1, sizeof(setV));
		for (array<int, 3> e: match[x]){
			setV[e[0]] = e[2];
		}
		for (int x = 0; x < n; x ++){
			if (setV[x] == -1){
				auto it = truEdges.lower_bound({x, -1, -1});
				while (!(it != truEdges.end())) std::this_thread::sleep_for(10s);
				truEdges.erase(it);
				assert((*it)[0] == x);
				setV[x] = (*it)[2];
			}
		}
		for (int x = 0; x < n; x ++){
			printf("%d ", setV[x] + 1);
		}
		printf("\n");
	}
}