#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define fr(i,n)     for(int i=0;i<n;i++)
#define frr(i,n)    for(int i=1;i<=n;i++)
#define ms(x,i) memset(x,i,sizeof(x))
#define dbg(x)  cout << #x << " = " << x << endl
#define all(x)  x.begin(),x.end()
#define gnl cout << endl
#define olar cout << "olar" << endl
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
typedef long long int ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef pair<ll,ll> pll;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f;
const int MAXN = 100100;
const ll mod = 1000000007;
typedef vector< vector<ll> > matrix;

matrix nodes;
ll n,m,k;

matrix operator*(matrix a, matrix b){

	int a1=a.size(),a2=a[0].size();
	int b1=b.size(),b2=b[0].size();

	matrix aux;
	aux.resize(a1);
	fr(i,a1)
		aux[i].resize(b2);

	fr(i,a1){
		fr(j,b2){
			aux[i][j]=0ll;
			fr(k,a2){
				aux[i][j]+=a[i][k]*b[k][j];
				aux[i][j]=aux[i][j]%mod;
			}
		}
	}

	return aux;

}

matrix gen_id(){
	matrix aux;
	aux.resize(n);
	fr(i,n){
		aux[i].resize(n);
		aux[i][i]=1ll;
	}
	return aux;
}

matrix fastxp(matrix a, ll b){

	matrix ans = gen_id();

	while(b>0){
		if(b%2)
			ans=a*ans;
		a=a*a;
		b=b/2;
	}

	return ans;

}

void print_matrix(matrix a){

	int x=a.size(),y=a[0].size();
	fr(i,x){
		fr(j,y){
			cout << a[i][j] << " ";
		}
		gnl;
	}

}

int main(){

	cin >> n >> m >> k;

	nodes.resize(n);

	fr(i,n)
		nodes[i].resize(n);

	fr(i,m){
		int a,b; cin >> a >> b;
		a--;b--;
		nodes[a][b]++;
		nodes[b][a]++;
	}

	matrix t = fastxp(nodes,k);
	//print_matrix(t);

	fr(i,n){
		for(int j=i+1;j<n;j++){
			if(t[i][j])
				cout << t[i][j];
			else
				cout << -1;
			cout << " ";
		}
		gnl;
	}

}