#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 rng(random_device{}()); 
const ll mod=1000000007;
//int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int inf=0x20202020;
typedef int flowt;
namespace flow {
	const int M=100000,N=1000;
	int y[M],nxt[M],gap[N],fst[N],c[N],pre[N],q[N],dis[N];
	flowt f[M];
	int S,T,tot,Tn;
	void init(int s,int t,int tn) {
		tot=1; assert(tn<N);
		rep(i,0,tn) fst[i]=0;
		S=s;T=t;Tn=tn;
	}
	void add(int u,int v,flowt c1,flowt c2=0) {
		tot++;y[tot]=v;f[tot]=c1;nxt[tot]=fst[u];fst[u]=tot;
		tot++;y[tot]=u;f[tot]=c2;nxt[tot]=fst[v];fst[v]=tot;
	}
	flowt sap() {
		int u=S,t=1;flowt flow=0;
		rep(i,0,Tn) c[i]=fst[i],dis[i]=Tn,gap[i]=0;
		q[0]=T;dis[T]=0;pre[S]=0;
		rep(i,0,t) {
			int u=q[i];
			for (int j=fst[u];j;j=nxt[j]) if (dis[y[j]]>dis[u]+1&&f[j^1]) 
				q[t++]=y[j],dis[y[j]]=dis[u]+1;
		}
		rep(i,0,Tn) gap[dis[i]]++;
		while (dis[S]<=Tn) {
			while (c[u]&&(!f[c[u]]||dis[y[c[u]]]+1!=dis[u])) c[u]=nxt[c[u]];
			if (c[u]) {
				pre[y[c[u]]]=c[u]^1;
				u=y[c[u]];
				if (u==T) {
					flowt minf=inf;
					for (int p=pre[T];p;p=pre[y[p]]) minf=min(minf,f[p^1]);
					for (int p=pre[T];p;p=pre[y[p]]) f[p^1]-=minf,f[p]+=minf;
					flow+=minf;u=S;
				}
			} else {
				if (!(--gap[dis[u]])) break;
				int mind=Tn;
				c[u]=fst[u];
				for (int j=fst[u];j;j=nxt[j]) if (f[j]&&dis[y[j]]<mind) 
					mind=dis[y[j]],c[u]=j;
				dis[u]=mind+1;
				gap[dis[u]]++;
				if (u!=S) u=y[pre[u]];
			}
		}
		return flow;
	}
};

const int N=5010;
VI used[N];
vector<VI> res;
bool mark[N*100];
void coloring(vector<vector<int>> edge) {
    int n=SZ(edge);
    int d=SZ(edge[0]);
    if (d==1) {
        VI pr;
        rep(i,0,n) pr.pb(edge[i][0]);
        res.pb(pr);
    } else if (d%2==0) {
        vector<vector<PII>> G(2*n);
        vector<int> cir;
        int tot=0;
        rep(i,0,n) rep(j,0,d) {
            int v=i,w=edge[i][j]+n;
            G[v].pb(mp(w,tot)); G[w].pb(mp(v,tot));
            ++tot;
        }
        vector<bool> vis1(2*n, false), vis2(tot, false);
        vector<PII> stk;
        for (int s = 0; s < 2*n; s++) if (!vis1[s]) {
            stk.clear();
            stk.emplace_back(s, -1);
            while (!stk.empty()) {
                int v, w, e; tie (v, e) = stk.back(); vis1[v] = true;
                if (G[v].empty()) { cir.emplace_back(e); stk.pop_back(); }
                else {
                    tie (w, e) = G[v].back(); G[v].pop_back();
                    if (!vis2[e]) { vis2[e] = true; stk.emplace_back(w, e); }
                }
            }
            cir.pop_back();
        }
        vector<VI> e1(n),e2(n);
        assert(SZ(cir)==n*d);
        rep(i,0,n*d) {
            int u=cir[i]/d;
            if (i%2==0) e1[u].pb(edge[u][cir[i]%d]);
            else e2[u].pb(edge[u][cir[i]%d]);
        }
        coloring(e1);
        coloring(e2);
    } else {
        vector<int> P(n),L(n,-1),R(n,0);
        rep(i,0,n) P[i]=i;
        shuffle(P.begin(),P.end(),rng);
        for(auto p0:P) {
            int p=p0;
            VI S;
            while (p!=-1) {
                int q=-1;
                do q=edge[p][rng()%d]; while(L[q]==p);
                while(mark[q]) mark[S.back()]=false,S.pop_back();
                p=L[q],mark[q]=true,S.pb(q);
            }
            p=p0;
            for(auto s:S)mark[s]=false,swap(p,L[s]);
        }
        VI pr;
        rep(i,0,n) R[L[i]]=i;
        rep(i,0,n) pr.pb(R[i]);
        rep(i,0,n) edge[i].erase(find(all(edge[i]),R[i]));
        res.pb(pr);
        coloring(edge);
    }
}

int n,m,c,k,id[N];
PII E[N];
vector<int> wt[222][222];
int main() {
	scanf("%d%d%d%d",&n,&m,&c,&k);
	rep(i,0,c) {
		int u,v;
		scanf("%d%d",&u,&v);
		--u; --v;
		E[i]=mp(u,v);
	}
	int l=0,r=c+1;
	auto check=[&](int x) {
		flow::init(n+m,n+m+1,n+m+2);
		rep(i,0,n) flow::add(n+m,i,x);
		rep(i,0,m) flow::add(i+n,n+m+1,x);
		rep(i,0,c) {
			id[i]=flow::tot+1;
			flow::add(E[i].fi,E[i].se+n,1);
		}
		int w=flow::sap();
		if (w<k*x) return false;
		rep(i,0,m) flow::add(i+n,n+m+1,inf);
		int w2=flow::sap();
		if (w+w2<n*x) return false;
		return true;
	};
	while (l+1<r) {
		int md=(l+r)>>1;
		if (check(md)) l=md; else r=md;
	}
	int x=l;
	printf("%d\n",x);
	if (x==0) {
		return 0;
	}
	check(x);
	rep(i,0,c) if (flow::f[id[i]]==0) {
		used[E[i].se].pb(i);
	}
	vector<VI> eg(n+m);
	int tl=n,tr=m,dg=0;
	rep(i,0,m) if (SZ(used[i])<x) {
		//printf("? %d\n",i);
		for (auto y:used[i]) {
			eg[E[y].fi].pb(i);
			wt[E[y].fi][i].pb(y);
		}
		rep(j,0,x-SZ(used[i])) {
			if (SZ(eg[tl])==x) tl++;
			eg[tl].pb(i);
		}
	} else {
		rep(j,0,x) {
			int y=used[i][j];
			eg[E[y].fi].pb(i);
			wt[E[y].fi][i].pb(y);
		}
		rep(j,x,SZ(used[i])) {
			if (dg==x) tr++,dg=0;
			int z=tr;
			int y=used[i][j];
			eg[E[y].fi].pb(z);
			wt[E[y].fi][z].pb(y);
			dg++;
		}
	}
	//printf("? %d %d\n",tl,tr);
	if (SZ(eg[tl])>0) {
		while (SZ(eg[tl])<x) {
			eg[tl].pb(tr),dg++;
		}
	}
	if (dg==x) tr++,dg=0;
	if (SZ(eg[tl])==x) ++tl;
	//printf("? %d %d %d\n",tl,tr,dg);
	assert(tl==tr&&dg==0);
	eg.resize(tl);
	coloring(eg);
	rep(i,0,x) {
		rep(u,0,n) {
			int v=res[i][u];
			assert(!wt[u][v].empty());
			printf("%d ",wt[u][v].back()+1); wt[u][v].pop_back();
		}
		puts("");
	}
}