#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl '\n'
#define log(...) (void(0))
#endif
using namespace std;
using ll = long long;
using lf = long double;
using ull = unsigned long long;
using pii = pair<int, int>;

const int N = 1e5 + 9;
const int M = 2e5 + 10;
const int mod = 1e9 + 7;
int T, n, m, k;
vector<int> g[N];
vector<pii> e;

namespace bf {
int n;
vector<pii> e, e_nxt;
vector<int> g[N];
int count() {
  vector<int> id(n + 1), rnk(n + 1);
  for (int i = 1; i <= n; i++) {
    g[i].clear();
    id[i] = i;
  }
  vector<int> deg(n + 1, 0);
  for (const auto &[u, v] : e) {
    // log("edge %d %d\n", u, v);
    ++deg[u], ++deg[v];
  }
  sort(1 + all(id), [&](int u, int v) { return deg[u] == deg[v] ? u < v : deg[u] < deg[v]; });
  for (int i = 1; i <= n; i++) {
    rnk[id[i]] = i;
  }
  for (auto [u, v] : e) {
    if (rnk[u] > rnk[v]) swap(u, v);
    g[u].emplace_back(v);
  }
  vector<int> mrk(n + 1);
  int ans = 0;
  for (int u = 1; u <= n; u++) {
    for (int v : g[u]) mrk[v] = 1;
    for (int v : g[u])
      for (int w : g[v])
        if (mrk[w]) {
          // log("find circ %d %d %d\n", u, v, w);
          ans++;
        }
    for (int v : g[u]) mrk[v] = 0;
  }
  return ans;
}
void makeL() {
  for (int i = 1; i <= n; i++) {
    g[i].clear();
  }
  for (int i = 0; i < sz(e); i++) {
    g[e[i].first].emplace_back(i + 1);
    g[e[i].second].emplace_back(i + 1);
  }
  for (int u = 1; u <= n; u++)
    for (int i = 0; i < sz(g[u]); i++)
      for (int j = i + 1; j < sz(g[u]); j++) {
        e_nxt.emplace_back(g[u][i], g[u][j]);
      }
  n = e.size();
  e.swap(e_nxt), e_nxt.clear();
}
pair<int, int> calc() {
  n = ::n;
  e = ::e;
  for (int i = 1; i <= k; i++) { // L(G)
    makeL();
  }
  int cnt = count();
  if (n == 0) return make_pair(0, 1);
  if (sz(e) == 0) return make_pair(1, n);
  if (cnt) return make_pair(3, cnt);
  return make_pair(2, sz(e));
}
pair<int, int> solve() {
  n = ::n;
  e = ::e;
  for (int i = 1; i < k; i++) { // L(G)
    makeL();
  }
  pair<int, int> ans = {INT_MIN, -1};
  vector<int> deg(n + 1);
  for (auto [u, v] : e) {
    ++deg[u], ++deg[v];
  }
  for (int i = 1; i <= n; i++) {
    if (deg[i] > ans.first) {
      ans = {deg[i], 1};
    } else if (deg[i] == ans.first) {
      ++ans.second;
    }
  }
  return ans;
}
} // namespace bf
int dd[N], de[M];
struct elem {
  int mx, cnt;
  elem operator+(const elem &y) const {
    if (mx < y.mx) return y;
    if (mx > y.mx) return *this;
    return (elem){mx, (cnt + y.cnt) % mod};
  }
  elem operator*(const elem &y) const { return (elem){mx + y.mx, (int)(1ll * cnt * y.cnt % mod)}; }
} ans;
vector<int> ar[N];
int mx[5], num[5], sz;
int C2(int x) { return (1ll * x * (x - 1) >> 1) % mod; }
elem Calc_3(vector<int> &x) {
  sz = 0;
  for (int i : x) {
    if (!sz || i < mx[sz]) {
      if (sz == 3) break;
      mx[++sz] = i, num[sz] = 1;
    } else
      ++num[sz];
  }
  if (num[1] >= 3) return (elem){mx[1] * 4 - 6, (int)(1ll * num[1] * C2(num[1] - 1) % mod)};
  if (num[1] == 2) return (elem){mx[1] * 3 + mx[2] - 6, 2 * num[2]};
  if (num[2] >= 2) return (elem){mx[1] * 2 + mx[2] * 2 - 6, C2(num[2])};
  return (elem){mx[1] * 2 + mx[2] + mx[3] - 6, num[3]};
}
elem Calc_2(vector<int> &x) {
  sz = 0;
  for (int i : x) {
    if (!sz || i < mx[sz]) {
      if (sz == 2) break;
      mx[++sz] = i, num[sz] = 1;
    } else
      ++num[sz];
  }
  if (num[1] >= 2) return (elem){mx[1] * 2, C2(num[1])};
  return (elem){mx[1] + mx[2], num[2]};
}
elem Calc_1(vector<int> &x, int del) {
  sz = 0;
  for (int i : x) {
    if (i == del) {
      del = -1;
      continue;
    }
    if (!sz) {
      sz = 1;
      mx[1] = i, num[1] = 1;
    } else if (i < mx[1]) {
      break;
    } else
      ++num[1];
  }
  return (elem){mx[1], num[1]};
}
#define clr(vec) (vector<int>().swap(vec))
void Solve_k4() {
  for (int i = 1; i <= n; ++i) clr(ar[i]);
  for (int i = 0; i < m; ++i) {
    ar[e[i].first].push_back(de[i]);
    ar[e[i].second].push_back(de[i]);
  }
  for (int i = 1; i <= n; ++i) {
    // log("i=%d\n", i);
    if (ar[i].empty()) continue;
    sort(all(ar[i]));
    reverse(all(ar[i]));
    if (ar[i].size() < 3) continue;
    ans = ans + Calc_3(ar[i]);
    log("ans=%d\n", ans.mx);
  }
  for (int i = 0; i < m; ++i) {
    if (min(ar[e[i].first].size(), ar[e[i].second].size()) < 2) continue;
    ans = ans + ((elem){2 * de[i] - 6, 1} * Calc_1(ar[e[i].first], de[i]) * Calc_1(ar[e[i].second], de[i]));
  }
}
void Solve_k3() {
  // log("n=%d\n", n);
  for (int i = 1; i <= n; ++i) clr(ar[i]);
  for (int i = 1; i <= n; ++i) {
    // log("---------i=%d\n", i);
    for (int j : g[i]) {
      ar[i].push_back(dd[j]);
    }
    if (ar[i].size() < 2) continue;
    sort(all(ar[i])), reverse(all(ar[i]));
    ans = ans + ((elem){dd[i] * 2 - 6, 1} * Calc_2(ar[i]));
    log("ans=%d,%d\n", ans.mx, ans.cnt);
  }
}
void Solve_k2() {
  for (int i = 0; i < m; ++i) {
    ans = ans + (elem){de[i], 1};
  }
}
void Solve_k1() {
  for (int i = 1; i <= n; ++i) {
    ans = ans + (elem){dd[i], 1};
  }
}
int main() {
#ifdef memset0
  // freopen("B.txt", "r", stdin);
  freopen("B.in", "r", stdin);
#endif
  // cin.tie(0)->sync_with_stdio(0);
  cin >> T;
  while (T--) {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) dd[i] = 0;
    for (int i = 0; i <= m; ++i) de[i] = 0;
    for (int u, v, i = 1; i <= m; i++) {
      cin >> u >> v;
      e.emplace_back(u, v);
      g[u].emplace_back(v);
      g[v].emplace_back(u);
      ++dd[u], ++dd[v];
    }
    for (int i = 0; i < m; ++i) {
      de[i] = dd[e[i].first] + dd[e[i].second] - 2;
    }
    ans = (elem){0, 0};
    if (k == 4) {
      Solve_k4();
    } else if (k == 3) {
      Solve_k3();
    } else if (k == 2) {
      Solve_k2();
    } else {
      Solve_k1();
    }
    log("! find ans %d %d\n", ans.mx, ans.cnt);
    if (ans.mx <= 3) {
      auto tmp = bf::calc();
      log("> find by bf %d %d\n", tmp.first, tmp.second);
      ans.mx = tmp.first, ans.cnt = tmp.second;
    }
#ifdef memset0
    if (ans.mx > 3) {
      auto tmp = bf::solve();
      cerr << tmp.first << " " << tmp.second << " bf" << endl;
      if (!(tmp.first == ans.mx && tmp.second == ans.cnt)) {
        cerr << ans.mx << " " << ans.cnt << " ans" << endl;
        cerr << n << " " << m << " " << k << endl;
        for (auto [u, v] : e) {
          cout << u << " " << v << endl;
        }
        cerr << "!!! failed !!!" << endl;
        exit(-1);
      }
    }
#endif
    cout << ans.mx << " " << ans.cnt << endl;
    // remember to clear
    e.clear();
    for (int i = 1; i <= n; i++) {
      g[i].clear();
    }
  }
}