#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=1000020;
int n,m,d[N];
vector<int> G[N],cg[N];
ll ans,tot;
struct Ans{
    int mx;
    ll tot;
};
Ans Merge(Ans a,Ans b){
    if(a.mx>b.mx)return a;
    if(b.mx>a.mx)return b;
    a.tot=(a.tot+b.tot)%mod;
    return a;
}
inline int C2(int x){
    return 1LL*x*(x-1)/2%mod;
}
inline int C3(int x){
    return 1LL*x*(x-1)*(x-2)/6%mod;
}
int k;
vector<pair<int,int> > H[N];
vector<pair<int,int> > E;
void Baoli(){
    for(int t=1;t<=k;++t){
        int z=E.size();
        for(int i=1;i<=n;++i){
            H[i].clear();
        }
        for(int i=0;i<(int)E.size();++i){
            int u=E[i].first,v=E[i].second;
            H[u].emplace_back(v,i+1);
            H[v].emplace_back(u,i+1);
        }
        vector<pair<int,int> > _E;
        for(int u=1;u<=n;++u){
            for(int i=0;i<(int)H[u].size();++i){
                for(int j=i+1;j<(int)H[u].size();++j){
                    _E.emplace_back(H[u][i].second,H[u][j].second);
                }
            }
        }
        n=z;
        E=_E;
    }
    for(int i=1;i<=n;++i)G[i].clear();
    for(auto [u,v]:E){
        G[u].push_back(v);
        G[v].push_back(u);
    }
    Ans ans={0,1};
    if(n)
        ans=Merge(ans,{1,n});
    if(E.size())
        ans=Merge(ans,{2,(int)E.size()});
    Ans now={3,0};
    vector<int> vis(n+1);
    for(int u=1;u<=n;++u){
        for(auto x:G[u])
            vis[x]++;
        for(auto x:G[u]){
            for(auto y:G[x]){
                if(y==u)
                    continue;
                now.tot=(now.tot+vis[y])%mod;
            }
        }
        for(auto x:G[u])
            vis[x]--;
    }
    now.tot/=6;
    if(now.tot)
        ans=Merge(ans,now);
    cout<<ans.mx<<' '<<ans.tot<<'\n';
}
void Solve(){
    cin>>n>>m>>k;
    E.clear();
    for(int i=1;i<=n;++i){
        cg[i].clear();
        G[i].clear();
    }
    for(int i=1;i<=m;++i){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
        E.emplace_back(u,v);
    }
    for(int i=1;i<=n;++i){
        d[i]=G[i].size();
    }
    for(int i=1;i<=n;++i){
        sort(G[i].begin(),G[i].end(),[&](int u,int v){return G[u].size()>G[v].size();});
        cg[i].resize(G[i].size());
        for(int j=(int)cg[i].size()-1;j>=0;--j){
            cg[i][j]=1;
            if(j+1<(int)cg[i].size()&&d[G[i][j]]==d[G[i][j+1]])cg[i][j]+=cg[i][j+1];
        }
    }
    Ans ans={0,0};
    if(k==1){
        for(int i=1;i<=n;++i){
            ans=Merge(ans,{d[i],1});
        }
    }
    else if(k==2){
        for(auto [u,v]:E){
            ans=Merge(ans,{d[u]+d[v]-2,1});
        }
    }
    else if(k==3){
        for(int u=1;u<=n;++u){
            if(d[u]<2)continue;
            Ans now;
            now.mx=2*d[u]+d[G[u][0]]+d[G[u][1]]-6;
            if(d[G[u][0]]==d[G[u][1]]){
                now.tot=C2(cg[u][0]);
            }
            else{
                now.tot=cg[u][1];
            }
            ans=Merge(ans,now);
        }
    }
    else{
        for(auto [u,v]:E){
            if(d[u]<2||d[v]<2)continue;
            Ans now;
            int x=G[u][0]==v?G[u][1]:G[u][0];
            int y=G[v][0]==u?G[v][1]:G[v][0];
            now.mx=3*(d[u]+d[v])+(d[x]+d[y])-14;
            int cx=(G[u][0]==v?cg[u][1]:(cg[u][0]-(d[x]==d[v])));
            int cy=(G[v][0]==u?cg[v][1]:(cg[v][0]-(d[y]==d[u])));
            now.tot=1ll*cx*cy%mod;
            // now.tot=1LL*cg[u][G[u][0]==v]*cg[v][G[v][0]==u]%mod;
            ans=Merge(ans,now);
        }
        for(int u=1;u<=n;++u){
            if(d[u]<3)continue;
            Ans now;
            int d2=d[G[u][0]];
            int d3=d[G[u][1]];
            int d4=d[G[u][2]];
            now.mx=4*d[u]+2*d[G[u][0]]+d[G[u][1]]+d[G[u][2]]-14;
            if(d2==d3){
                if(d3==d4){
                    now.tot=1LL*C2(cg[u][0]-1)*cg[u][0]%mod;
                }
                else{
                    now.tot=2*cg[u][2];
                }
            }
            else{
                if(d3==d4){
                    now.tot=C2(cg[u][1]);
                }
                else{
                    now.tot=cg[u][2];
                }
            }
            ans=Merge(ans,now);
        }
    }
    if(ans.mx<=3){
        Baoli();
        return;
    }
    cout<<ans.mx<<' '<<ans.tot<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--)
        Solve();
    return 0;
}