#include<stdio.h>
#include<vector>
using namespace std;
#define N 55
vector <int> V[N];
int n;
int A[N], B[N];

int ff(int mm){
	int i, s = 1;
	//rintf("%d",mm);
	for(i=0;i<V[mm].size();i++){
		if(A[V[mm][i]]==0){
			A[V[mm][i]]=2;
			s = s+ff(V[mm][i]);
		}
	}
	return s;
}
void f(int k, int m){
	int i, p; 
	
	if(k==0){
		p = ff(1);
		B[p]++;
		if(p==1){
			for(i=1;i<=n;i++) if(A[i]==1) printf("%d ",i);
			printf("\n");
		}
		for(i=0;i<=n;i++) if(A[i]==2) A[i] = 0;
		return;
	}
	for(i=m;i<=n;i++){
		if(A[i]==0){
			A[i]=1;
			f(k-1, i);
			A[i]=0;
		}
	}
}
int main(){
	int m, k, a, b,i ;
	scanf("%d %d %d", &n, &m, &k);
	for(i=0;i<m;i++){
		scanf("%d %d", &a, &b);
		V[a].push_back(b);
	}
	f(k, 2);
	for(i=1;i<=n;i++){
		if(B[i]>0){
			printf("%d %d", i, B[i]);
			return 0;
		}
	}
}