时间限制: 1 Sec 内存限制: 128 MB

题目描述
魔法宫殿的最深处藏着一把万能权杖，为这个国家提供了强大的军事力量，然而有天却被一个等级略低的小法师误用，导致强大的法术失控，并形成了一个怪异的法阵保护着法杖。国家少了一件圣器，在战火纷飞的年代国力也逐渐衰退，历代国王们不惜一切代价和奖赏，吸引人们来破解法阵，可惜百年来无人能破。现在你穿越来到了宫殿，这个法阵就摆在你面前，它由许多魔法球连接而成，你可以看成一张联通的无向图，由于这个世界的元素是平衡的，相邻的魔法球如果具有相同的元素，就会发出元素之力伤害周围的人，当然，问题还不止这么简单，你不仅仅要使相邻魔法球之间的元素互不相同，还得知道对于K种元素，有多少种方案可以满足这个条件，听完国王的描述，你一言不发，掏出笔记本，打开编译器……

输入
第一行输入三个正整数N, M, K（N <= 50, M <= 1000, 2<=K <= 4），分别表示点的个数，边的个数，元素数量，第2行到第1 + M行，每行两个正整数U, V（U <= N, V <= N且U != V）， 表示U到V有一条双向边，图保证联通。

输出
一个整数，表示用最多K种元素赋予魔法球的方案数，答案对1e9 + 7取模

样例输入
4 5 4
1 4
1 2
1 3
3 4
3 2
样例输出
48

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mod=1e9+7;
ll n,m,k;
ll a[100][100];
ll sum=0,v[100];
int ok(int kx,int col){
    for(int i=1;i<=n;i++){
        if(a[kx][i]&&(col==v[i]))return 0;
    }
    return 1;
}
void dfs(int x){
    if(x>n){
        sum++;
        sum%=mod;
        return ;
    }
    for(int i=1;i<=k;i++){

        if(!ok(x,i)){
            continue;
        }
        v[x]=i;
        dfs(x+1);
        v[x]=0;
    }
    return ;
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        a[x][y]=1;
        a[y][x]=1;
    }
    dfs(1);
    sum%=mod;
    cout<<sum;
	return 0;
}