#include<bits/stdc++.h>
using namespace std;
int n,k,m,total;
int a[110][110],b[110];
bool check(int numm,int color)
{
if(numm==1) return 1;
bool flag=0;
for(int i=1;i<numm;i++)
if((a[numm][i]&&b[i]!=color)||(!a[numm][i])) flag=1;
else {
flag=0;
break;
}
return flag;
}
void dfs(int num)
{
if(num>n)
{
total++;
return ;
}
for(int i=1;i<=m;i++)
if(check(num,i))
{
b[num]=i;
dfs(num+1);
}
}
int main()
{
cin>>n>>k>>m;
int x,y;
for(int i=1;i<=k;i++)
{
cin>>x>>y;
a[x][y]=a[y][x]=1;
}
dfs(1);
cout<<total<<endl;
return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,k,m,total;
int a[110][110],b[110];
void init()
{
cin>>n>>k>>m;
int x,y;
for(int i=1;i<=k;i++)
{
cin>>x>>y;
a[x][y]=a[y][x]=1;
}
}
bool check(int numm,int color)
{
if(numm==1) return true;
bool flag=false;
for(int i=1;i<numm;i++)
if((a[numm][i]&&b[i]!=color)||(!a[numm][i])) flag=true;
else {
flag=false;
break;
}
return flag;
}
void dfs(int num)
{
if(num>n)
{
total++;
return ;
}
for(int i=1;i<=m;i++)
if(check(num,i))
{
b[num]=i;
dfs(num+1);
}
}
int main()
{
init();
dfs(1);
cout<<total<<endl;
return 0;
}