好久没有做过图论题了……
考虑(k)次方的组合意义，实际上，要求的所有方案中导出子图边数的(k)次方，等价于有顺序地选出其中(k)条边，计算它们在哪一些图中出现过，将所有方案计算出来的答案加起来。
对于(k)条边来说，如果它们占据了(x)个点，那么它们就会出现在(2^{n-x})张图中。
那么(k=1)答案显然是(m imes 2^{n-2})
(k=2)时有(3)种情况：①两条边重合，等价于(k=1)；②两条边不重合但共一个顶点，对于一条边((s,t))，这种情况的出现的次数为(d_s + d_t - 2)；③两条边不重合且不共顶点，等于(M^2)减上面两种情况的出现次数。
(k=3)时情况比较多：①三条边重合，等价于(k=1)；②其中有一对边重合，等价于(k=2)；③三元环，使用三元环计数计算；
④三条边共占据(4)个点：有(A ightarrow B ightarrow C ightarrow D)和(A ightarrow B , A ightarrow C , A ightarrow D)两种情况。第一种情况可以枚举(BC)边，那么出现次数就是((d_B - 1) imes (d_C - 1))，注意有可能出现(AD)共点形成三元环的情况，所以在最后需要减掉(3 imes)三元环个数；第二种情况直接枚举点(A)。
⑤三条边共占据(5)个点，即(A ightarrow B ightarrow C , D ightarrow E)的情况。可以枚举(B)，那么方案数就是(d_B(d_B - 1)(M - 2))。注意在这个时候会有③和④的情况重算，记得减掉。
⑥三条边两两没有共顶点，这个就是$M^3 - $①②③④⑤
三元环计数求一下③这道题就做完了。时间复杂度(O(M sqrt{M}))。注意④⑤中重算部分的系数。
下面的代码里(k=3)的情况③④⑤⑥都是算的无序的；可能上面的描述里有序和无序有混淆，麻烦注意。
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int a = 0;
char c = getchar();
while(!isdigit(c)) c = getchar();
while(isdigit(c)){
a = a * 10 + c - 48;
c = getchar();
}
return a;
}
#define int long long
const int MAXN = 1e5 + 7 , MOD = 1e9 + 7;
int N , M , K , s[MAXN] , t[MAXN] , in[MAXN] , pow2[MAXN];
inline int poww2(int b){return b < 0 ? 0 : pow2[b];}
inline int poww(int a , int b){
int times = 1;
while(b){
if(b & 1) times = times * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return times;
}
namespace solve1{
int main(){return poww2(N - 2) * M % MOD;}
}
namespace solve2{
int main(){
int ans = solve1::main();
for(int i = 1 ; i <= M ; ++i){
ans = (ans + (in[s[i]] + in[t[i]] - 2) * poww2(N - 3) + (M - 1 - (in[s[i]] + in[t[i]] - 2)) * poww2(N - 4)) % MOD;
}
return ans;
}
}
namespace solve3{
int col[MAXN];
vector < int > ch[MAXN];
int calc3(){
int cnt = 0;
for(int i = 1 ; i <= M ; ++i)
if(in[s[i]] < in[t[i]] || (in[s[i]] == in[t[i]] && s[i] < t[i]))
ch[s[i]].push_back(t[i]);
else ch[t[i]].push_back(s[i]);
for(int i = 1 ; i <= N ; ++i){
for(auto p : ch[i]) col[p] = i;
for(auto p : ch[i])
for(auto q : ch[p])
if(col[q] == i) ++cnt;
}
return cnt % MOD;
}
int main(){
int ans = solve2::main() , tmp = solve1::main();
ans = ((ans - tmp + MOD) * 3 + tmp) % MOD;
int cnt3 = calc3() , cnt4 = MOD - cnt3 * 3 % MOD , cnt5 = 0 , cnt6 = 0;
for(int i = 1 ; i <= N ; ++i)
cnt4 = (cnt4 + in[i] * (in[i] - 1) * (in[i] - 2) / 6) % MOD;
for(int i = 1 ; i <= M ; ++i)
cnt4 = (cnt4 + (in[s[i]] - 1) * (in[t[i]] - 1)) % MOD;
cnt5 = MOD - (cnt4 * 2 + cnt3 * 3) % MOD;
for(int i = 1 ; i <= N ; ++i)
cnt5 = (cnt5 + MOD - in[i] * (in[i] - 1) * (in[i] - 2) / 6 % MOD) % MOD;
for(int i = 1 ; i <= N ; ++i)
cnt5 = (cnt5 + in[i] * (in[i] - 1) * (M - 2) / 2) % MOD;
cnt6 = (M * (M - 1) * (M - 2) / 6 - cnt5 - cnt4 - cnt3) % MOD;
return (ans + 6 * (cnt3 * poww2(N - 3) + cnt4 * poww2(N - 4) + cnt5 * poww2(N - 5) + cnt6 * poww2(N - 6))) % MOD;
}
}
signed main(){
pow2[0] = 1;
for(int i = 1 ; i <= 100000 ; ++i)
pow2[i] = (pow2[i - 1] << 1) % MOD;
for(int T = read() ; T ; --T){
N = read(); M = read(); K = read();
memset(in , 0 , sizeof(int) * (N + 1));
memset(solve3::col , 0 , sizeof(int) * (N + 1));
for(int i = 1 ; i <= N ; ++i)
solve3::ch[i].clear();
for(int i = 1 ; i <= M ; ++i){
s[i] = read(); t[i] = read();
++in[s[i]]; ++in[t[i]];
}
if(K == 1) cout << solve1::main() << endl;
else if(K == 2) cout << solve2::main() << endl;
else cout << solve3::main() << endl;
}
return 0;
}