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 namespace std;
template <class T>
bool mmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool mmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
void yesno(bool c) { cout << (c ? "YES" : "NO") << '\n'; }
void yes() { yesno(true); }
void no() { yesno(false); }
void imp() { cout << "-1" << '\n'; }
const int inf = 0x3f3f3f3f;
const long long infl = 0x3f3f3f3f3f3f3f3f;
struct base_graph {
  int n, ecnt = 0;
  vector<int> from, to;
  vector<long long> w;
  bool is_wei;
  base_graph(int n, bool is_wei = false) : n(n), is_wei(is_wei) {}
  virtual int add(int a, int b, long long ww = 0) = 0;
  int base_add(int a, int b, long long ww = 0) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    from.push_back(a);
    to.push_back(b);
    if (is_wei) w.push_back(ww);
    return ecnt++;
  }
  void readin(int m, bool add_rev = false, int offset = 1) {
    reserve(add_rev ? 2 * m : m);
    for (int i = 0; i < m; i++) {
      int a, b, ww = 0;
      cin >> a >> b;
      a -= offset;
      b -= offset;
      if (is_wei) cin >> ww;
      add(a, b, ww);
      if (add_rev) add(b, a, ww);
    }
  }
  void readin_tree(bool add_rev, int offset = 1) {
    int m = n - 1;
    reserve(add_rev ? 2 * m : m);
    for (int i = 2; i <= m; i++) {
      int p;
      cin >> p;
      int a = i - offset;
      add(a, p);
      if (add_rev) add(p, a);
    }
  }

 protected:
  void reserve(int m) {
    from.reserve(m);
    to.reserve(m);
    if (is_wei) w.reserve(m);
  }
};
struct my_hash {
  const uint64_t RANDOM =
      chrono::steady_clock::now().time_since_epoch().count();
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const { return splitmix64(x + RANDOM); }
};
using myset = unordered_set<int, my_hash>;
struct undir_graph : public base_graph {
  vector<vector<pair<int, int>>> edg;
  undir_graph(int n, bool is_wei = false) : base_graph(n, is_wei), edg(n) {}
  int add(int a, int b, long long ww = 0) {
    if (b > a) swap(a, b);
    int e = base_add(a, b, ww);
    edg[a].push_back({e, b});
    edg[b].push_back({e, a});
    return e;
  }
  void readin(int m, int offset = 1) { base_graph::readin(m, false, offset); }
  void readin_tree(int offset = 1) { base_graph::readin_tree(false, offset); }
};
template <class T, class Comp = less<T>>
struct prioset {
  using P = pair<T, int>;
  struct pcomp {
    Comp cmp;
    bool operator()(const P& lhs, const P& rhs) const {
      if (lhs.first == rhs.first) return lhs.second < rhs.second;
      return cmp(lhs.first, rhs.first);
    }
  };
  set<P, pcomp> s;
  unordered_map<int, T> m;
  void push(T val, int id) {
    if (m.count(id)) {
      s.erase({m[id], id});
    }
    s.insert({val, id});
    m[id] = val;
  }
  void pop() {
    m.erase(s.begin()->second);
    s.erase(s.begin());
  }
  T topval() { return s.begin()->first; }
  T topvalpop() {
    T ans = topval();
    pop();
    return ans;
  }
  int topid() { return s.begin()->second; }
  int topidpop() {
    int ans = topid();
    pop();
    return ans;
  }
  P top() { return *s.begin(); }
  P toppop() {
    P ans = top();
    pop();
    return ans;
  }
  int size() { return s.size(); }
  bool empty() { return s.size() == 0; }
};
using uset = myset;
void solve() {
  int n, m, k;
  cin >> n >> m >> k;
  undir_graph g(n);
  g.readin(m);
  for (int i = 0; i < (n); i++) sort((g.edg[i]).begin(), (g.edg[i]).end());
  vector<myset> edg(n);
  for (int i = 0; i < (n); i++)
    for (auto [e, v] : g.edg[i]) edg[i].insert(v);
  vector<int> deg(n), alive(n, 1);
  for (int i = 0; i < (n); i++) deg[i] = ((int)(edg[i]).size());
  prioset<int> s;
  for (int i = 0; i < (n); i++) {
    s.push(deg[i], i);
  }
  while (!s.empty()) {
    int u = s.topid();
    int val = s.topval();
    if (val >= k - 1) break;
    s.pop();
    alive[u] = 0;
    for (auto v : edg[u]) {
      if (!alive[v]) continue;
      deg[v]--;
      s.push(deg[v], v);
    }
  }
  while (!s.empty()) {
    int u = s.topid();
    int val = s.topval();
    s.pop();
    ;
    alive[u] = false;
    if (val >= k) {
      cout << 1 << " " << (((int)(s).size()) + 1) << '\n';
      cout << (u + 1) << " ";
      while (!s.empty()) {
        cout << (s.topid() + 1) << " ";
        s.pop();
      }
      cout << '\n';
      return;
    } else if (val < k - 1) {
      for (auto v : edg[u]) {
        if (!alive[v]) continue;
        deg[v]--;
        s.push(deg[v], v);
      }
    } else {
      vector<int> group;
      group.push_back(u);
      for (auto v : edg[u]) {
        if (alive[v]) group.push_back(v);
      }
      int ok = 1;
      for (int i = 0; i < ((int)(group).size()); i++) {
        for (int j = i + 1; j < ((int)(group).size()); j++) {
          if (edg[group[i]].find(group[j]) == edg[group[i]].end()) {
            ok = 0;
            break;
          }
        }
      }
      if (ok) {
        cout << 2 << '\n';
        for (int v : group) {
          cout << (v + 1) << " ";
        }
        cout << '\n';
        return;
      }
      for (auto v : edg[u]) {
        if (!alive[v]) continue;
        deg[v]--;
        s.push(deg[v], v);
      }
    }
  }
  imp();
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tc = 1;
  cin >> tc;
  while (tc--) solve();
  return 0;
}