#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 2147483646
#define inf 9223372036854775806
#define pl putchar('\n');
int n,m,c;
int color[105];
vector<int> g[105];
int ans=0;
bool mark[2505];
int color_[105];
void dfs(int x){
	cout<<x<<":";
	if(x==n+1){
		ans++;
		return;
	}
	for(int i=1;i<=c;i++){
		mark[i]=1;
	}
	for(int i=0;i<g[x].size();i++){
		mark[color_[g[x][i]]]=0;
	}
	for(int i=1;i<=c;i++){
		if(mark[i]){
			cout<<i<<endl;
			color_[x]=i;
			dfs(x+1);
			color_[x]=0;
		}
	}
	return;
}
int main(){
	system("cls");
	freopen("P2819 图的 m 着色问题程序输出.txt","w",stdout);
    cin>>n>>m>>c;
    for(int i=1;i<=m;i++){
    	int a,b;
    	cin>>a>>b;
    	g[a].push_back(b);
    	g[b].push_back(a);
	}
	dfs(1);
	cout<<ans;
    return 0;
}