#include<iostream>
#include<cstdio>
#include<vector>
#define N 150
#define M 22500
#define K 1000000
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int n,m,k,nt[N+1],nt2[N+1],nts[N+1],nts2[N+1],X[M+1],Y[M+1],cl[M+1],cls[M+1],c[M+1][N+1],snum[N+1][N+1],num[N+1][N+1],num2[N+1][N+1],tong[N+1],length;
vector<int>p[K+1];
vector<int>E[N+1];
vector<int>E2[N+1];
void adder(int x,int y)
{
	int l1=0,l2=0,op=0;
	for (int i=1;i<=k;++i)
	{
		if (!num[x][i]&&!num2[y][i])
		{
			num[x][i]=y,num2[y][i]=x;
			return;
		}
		if (!num[x][i]) l1=i;
		if (!num2[y][i]) l2=i;
	}
	length=0;
	if (l1<l2) tong[++length]=x,tong[++length]=y;
	else tong[++length]=y,tong[++length]=x;
	while (1)
	{
		if ((!op)^(l1>l2))
		{
			if (num2[y][l1]) x=num2[y][l1],tong[++length]=x;
			else break;
		}
		else
		{
			if (num[x][l2]) y=num[x][l2],tong[++length]=y;
			else break;
		}
		op^=1;
	}
	for (int i=2;i+1<=length;++i)
	{
		if ((!(i&1))^(l1>l2)) num2[tong[i]][l1]=num[tong[i+1]][l1]=0;
		else num[tong[i]][l2]=num2[tong[i+1]][l2]=0;
	}
	for (int i=1;i+1<=length;++i)
	{
		if ((i&1)^(l1>l2)) num[tong[i]][l1]=tong[i+1],num2[tong[i+1]][l1]=tong[i];
		else num2[tong[i]][l2]=tong[i+1],num[tong[i+1]][l2]=tong[i];
	}
	return;
}
int main()
{
	int d;
	bool op;
	n=read(),m=read(),k=read();
	for (int i=1;i<=m;++i)
	{
		X[i]=read(),Y[i]=read(),snum[X[i]][Y[i]]=i,adder(X[i],Y[i]);
		for (int j=1;j<=k;++j) c[i][j]=read();
	}
	for (int i=1;i<=n;++i)
		for (int j=1;j<=k;++j)
			if (num[i][j])
				cl[snum[i][num[i][j]]]=j;
	for (int i=1;i<=k;++i)
		for (int j=1;j<=n;++j)
			if (num[j][i])
			{
				d=snum[j][num[j][i]];
				for (int t=1;t<=k;++t) p[c[d][t]].push_back(d);
			}
	for (int i=1;i<=K;++i)
	{
		for (int j=1;j<=n;++j) E[j].clear(),E2[j].clear(),nts[j]=nts2[j]=0;
		for (int j=0;j<p[i].size();++j)
			if (!cls[p[i][j]])
				E[X[p[i][j]]].push_back(Y[p[i][j]]),E2[Y[p[i][j]]].push_back(X[p[i][j]]);
		while (1)
		{
			op=0;
			for (int j=1;j<=n;++j)
				if (!nts[j])
				{
					if (!E[j].empty()) nt[j]=E[j].back(),op=1;
					else nt[j]=0;
				}
			if (!op) break;
			for (int j=1;j<=n;++j)
			{
				nt2[j]=0;
				for (int t=0;t<E2[j].size();++t)
					if (nt[E2[j][t]]==j)
					{
						nt2[j]=E2[j][t];
						break;
					}
			}
			for (int j=1;j<=n;++j)
				if (nt2[j])
				{
					nts[nts2[j]]=0,nts[nt2[j]]=j,nts2[j]=nt2[j];
					while (E2[j].back()!=nt2[j]) E2[j].pop_back();
					E2[j].pop_back();
				}
			for (int j=1;j<=n;++j)
				if (!nts[j]&&!E[j].empty())
					E[j].pop_back();
		}
		for (int j=1;j<=n;++j)
			if (nts[j])
				cls[snum[j][nts[j]]]=i;
	}
	for (int i=1;i<=m;++i) printf("%d ",cls[i]);
	puts("");
	return 0;
}