Problem: You are given an undirected graph with n vertices and m edges. Also, you are given an integer k.

Find either a clique of size k or a non-empty subset of vertices such that each vertex of this subset has at least k neighbors in the subset. If there are no such cliques and subsets report about it.

A subset of vertices is called a clique of size k if its size is k and there exists an edge between every two vertices from the subset. A vertex is called a neighbor of the other vertex if there exists an edge between them.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^5) — the number of test cases. The next lines contain descriptions of test cases.

The first line of the description of each test case contains three integers n, m, k (1 ≤ n, m, k ≤ 10^5, k ≤ n).

Each of the next m lines contains two integers u, v (1 ≤ u, v ≤ n, u ≠ v), denoting an edge between vertices u and v.

It is guaranteed that there are no self-loops or multiple edges. It is guaranteed that the sum of n for all test cases and the sum of m for all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case: 

If you found a subset of vertices such that each vertex of this subset has at least k neighbors in the subset in the first line output 1 and the size of the subset. On the second line output the vertices of the subset in any order.

If you found a clique of size k then in the first line output 2 and in the second line output the vertices of the clique in any order.

If there are no required subsets and cliques print -1.

If there exists multiple possible answers you can print any of them.

Example

Input


3
5 9 4
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
10 15 3
1 2
2 3
3 4
4 5
5 1
1 7
2 8
3 9
4 10
5 6
7 10
10 8
8 6
6 9
9 7
4 5 4
1 2
2 3
3 4
4 1
1 3


Output


2
4 1 2 3 
1 10
1 2 3 4 5 6 7 8 9 10 
-1

Note

In the first test case: the subset \{1, 2, 3, 4\} is a clique of size 4.

In the second test case: degree of each vertex in the original graph is at least 3. So the set of all vertices is a correct answer.

In the third test case: there are no cliques of size 4 or required subsets, so the answer is -1.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using std::cin;
using std::cout;
const int N = 100054, M = N * 2;
int V, E, K, Es = 0;
int to[M], first[N], next[M];
int deg[N], deg_raw[N];
int que[N];
int len = 0, ans[N];
int stamp = 0, tag[N];
bool alive[N];
std::unordered_set<unsigned long long> S;
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
                    std::greater<std::pair<int, int>>>
    pq;
inline void addedge(int u, int v) {
  to[++Es] = v, next[Es] = first[u], first[u] = Es, ++deg[u];
  to[++Es] = u, next[Es] = first[v], first[v] = Es, ++deg[v];
}
inline bool check(int u, int v) {
  return S.count(u < v ? u | (unsigned long long)v << 32
                       : v | (unsigned long long)u << 32);
}
void work() {
  int i, j, u, v, x, y, h, t = 0;
  cin >> V >> E >> K, Es = len = 0;
  memset(deg, 0, (V + 1) << 2);
  memset(first, 0, (V + 1) << 2);
  memset(alive, true, V + 1);
  S.clear();
  for (i = 1; i <= E; ++i) {
    cin >> u >> v, addedge(u, v);
    if (u > v) std::swap(u, v);
    S.emplace(u | (unsigned long long)v << 32);
  }
  if (K == 1) {
    cout << "2\n1\n";
    return;
  }
  memcpy(deg_raw, deg, (V + 1) << 2);
  for (i = 1; i <= V; ++i)
    if (deg[i] < K) que[t++] = i;
  for (h = 0; h < t; ++h) {
    alive[x = que[h]] = false;
    for (i = first[x]; i; i = next[i])
      if (alive[y = to[i]] && --deg[y] == K - 1) que[t++] = y;
  }
  if (t < V) {
    for (i = 1; i <= V; ++i)
      if (alive[i]) ans[len++] = i;
    cout << '1' << ' ' << len << '\n';
    for (i = 0; i < len; ++i) cout << ans[i] << (i == len - 1 ? '\n' : ' ');
    return;
  }
  if (K * (K - 1ll) > 2 * E) {
    cout << "-1\n";
    return;
  }
  memcpy(deg, deg_raw, (V + 1) << 2);
  memset(alive, true, V + 1);
  for (t = 0, i = 1; i <= V; ++i)
    if (deg[i] < K - 1) que[t++] = i;
  for (h = 0; h < t; ++h) {
    alive[x = que[h]] = false;
    for (i = first[x]; i; i = next[i])
      if (alive[y = to[i]] && --deg[y] == K - 2) que[t++] = y;
  }
  if (t <= V - K) {
    for (; !pq.empty(); pq.pop())
      ;
    for (i = 1; i <= V; ++i)
      if (alive[i] && deg[i] < K) pq.emplace(deg[i], i);
    for (; !pq.empty();) {
      std::tie(v, x) = pq.top(), pq.pop();
      if (deg[x] != v) continue;
      alive[x] = false;
      if (deg[x] == K - 1) {
        len = 0, ans[len++] = x;
        for (i = first[x]; i; i = next[i])
          if (alive[y = to[i]]) ans[len++] = y;
        assert(len == K), ++stamp;
        for (i = 0; i < K; ++i)
          if (tag[ans[i]] = stamp, deg[ans[i]] < K - 1) break;
        if (i == K) {
          if (K < 120) {
            for (i = 0; i < K - 1; ++i) {
              for (j = i + 1; j < K; ++j)
                if (!check(ans[i], ans[j])) break;
              if (j < K) break;
            }
          } else {
            int cnt = 0;
            for (i = 1; i <= Es; i += 2)
              if (tag[to[i]] == stamp && tag[to[i + 1]] == stamp) ++cnt;
            i = (cnt == K * (K - 1) / 2 ? K - 1 : -1);
          }
          if (i == K - 1) {
            cout << '2' << '\n';
            for (i = 0; i < len; ++i)
              cout << ans[i] << (i == len - 1 ? '\n' : ' ');
            return;
          }
        }
      }
      for (i = first[x]; i; i = next[i])
        if (alive[y = to[i]] && --deg[y] < K) pq.emplace(deg[y], y);
    }
  }
  cout << "-1\n";
}
int main() {
  int T;
  std::ios::sync_with_stdio(false), cin.tie(NULL);
  for (cin >> T; T; --T) work();
  return 0;
}