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;
using ll = long long;
using ld = long double;
using db = double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
template <class T>
using V = vector<T>;
template <class T, size_t SZ>
using AR = array<T, SZ>;
template <class T>
using PR = pair<T, T>;
const int MOD = 1e9 + 7;
const int MX = 2e5 + 5;
const ll INF = 1e18;
const ld PI = acos((ld)-1);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
constexpr int pct(int x) { return __builtin_popcount(x); }
constexpr int bits(int x) { return 31 - __builtin_clz(x); }
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); }
ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
template <class T, class U>
T fstTrue(T lo, T hi, U first) {
  hi++;
  assert(lo <= hi);
  while (lo < hi) {
    T mid = lo + (hi - lo) / 2;
    first(mid) ? hi = mid : lo = mid + 1;
  }
  return lo;
}
template <class T, class U>
T lstTrue(T lo, T hi, U first) {
  lo--;
  assert(lo <= hi);
  while (lo < hi) {
    T mid = lo + (hi - lo + 1) / 2;
    first(mid) ? lo = mid : hi = mid - 1;
  }
  return lo;
}
template <class T>
void remDup(vector<T>& v) {
  sort(begin(v), end(v));
  v.erase(unique(begin(v), end(v)), end(v));
}
template <class T, class U>
void erase(T& t, const U& u) {
  auto it = t.find(u);
  assert(it != end(t));
  t.erase(it);
}
template <class T>
void re(complex<T>& c);
template <class T, class U>
void re(pair<T, U>& p);
template <class T>
void re(vector<T>& v);
template <class T, size_t SZ>
void re(AR<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(db& d) {
  str t;
  re(t);
  d = stod(t);
}
void re(ld& d) {
  str t;
  re(t);
  d = stold(t);
}
template <class T, class... U>
void re(T& t, U&... u) {
  re(t);
  re(u...);
}
template <class T>
void re(complex<T>& c) {
  T a, b;
  re(a, b);
  c = {a, b};
}
template <class T, class U>
void re(pair<T, U>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& x) {
  for (auto& a : x) re(a);
}
template <class T, size_t SZ>
void re(AR<T, SZ>& x) {
  for (auto& a : x) re(a);
}
template <class T>
void rv(int& n, vector<T>& x) {
  re(n);
  x.resize(n);
  for (auto& a : x) re(a);
}
str to_string(char c) { return str(1, c); }
str to_string(const char* second) { return (str)second; }
str to_string(str second) { return second; }
str to_string(bool b) { return to_string((int)b); }
template <class T>
str to_string(complex<T> c) {
  stringstream ss;
  ss << c;
  return ss.str();
}
str to_string(vector<bool> v) {
  str res = "{";
  for (int i = (0); i < ((int)(v).size()); ++i) res += char('0' + v[i]);
  res += "}";
  return res;
}
template <size_t SZ>
str to_string(bitset<SZ> b) {
  str res = "";
  for (int i = (0); i < (SZ); ++i) res += char('0' + b[i]);
  return res;
}
template <class T, class U>
str to_string(pair<T, U> p);
template <class T>
str to_string(T v) {
  bool fst = 1;
  str res = "";
  for (const auto& x : v) {
    if (!fst) res += " ";
    fst = 0;
    res += to_string(x);
  }
  return res;
}
template <class T, class U>
str to_string(pair<T, U> p) {
  return to_string(p.first) + " " + to_string(p.second);
}
template <class T>
void pr(T x) {
  cout << to_string(x);
}
template <class T, class... U>
void pr(const T& t, const U&... u) {
  pr(t);
  pr(u...);
}
void ps() { pr("\n"); }
template <class T, class... U>
void ps(const T& t, const U&... u) {
  pr(t);
  if (sizeof...(u)) pr(" ");
  ps(u...);
}
void DBG() { cerr << "]" << endl; }
template <class T, class... U>
void DBG(const T& t, const U&... u) {
  cerr << to_string(t);
  if (sizeof...(u)) cerr << ", ";
  DBG(u...);
}
void setIn(str second) { freopen(second.c_str(), "r", stdin); }
void setOut(str second) { freopen(second.c_str(), "w", stdout); }
void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
void setIO(str second = "") {
  unsyncIO();
  if ((int)(second).size()) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
int deg[100001];
vector<int> adj[100001];
bool alive[100001];
vector<pi> vals[100001];
unordered_set<int> m[100001];
vector<pi> checks[100001];
bool src[100001];
vector<int> pods[100001];
vector<int> tmp;
void rese(int n) {
  for (int i = 0; i < n; i++) {
    deg[i] = 0;
    adj[i].clear();
    adj[i].shrink_to_fit();
    vals[i].clear();
    vals[i].shrink_to_fit();
    checks[i].clear();
    checks[i].shrink_to_fit();
    pods[i].clear();
    pods[i].shrink_to_fit();
    m[i].clear();
  }
}
bool get_pod(int x, int k) {
  tmp.clear();
  for (int i = 0; i < adj[x].size(); i++) {
    int to = adj[x][i];
    if (deg[to] >= k - 1 && alive[to]) {
      tmp.push_back(to);
    }
  }
  if (tmp.size() == k - 1) {
    for (int a = 0; a < tmp.size(); a++) {
      for (int b = a + 1; b < tmp.size(); b++) {
        int x = tmp[a];
        int y = tmp[b];
        if (x > y) {
          swap(x, y);
        }
        if (m[x].find(y) == m[x].end()) {
          return false;
        }
      }
    }
    cout << "2\n";
    cout << (x + 1);
    for (int i = 0; i < k - 1; i++) {
      cout << " " << (tmp[i] + 1);
    }
    cout << "\n";
    return true;
  }
  return false;
}
int main() {
  setIO();
  int cases;
  cin >> cases;
  for (int q = 1; q <= cases; q++) {
    int n, mm, k;
    cin >> n >> mm >> k;
    rese(n);
    for (int i = 0; i < mm; i++) {
      int a, b;
      cin >> a >> b;
      if (a > b) {
        swap(a, b);
      }
      a--;
      b--;
      adj[a].push_back(b);
      adj[b].push_back(a);
      m[a].insert(b);
      deg[a]++;
      deg[b]++;
    }
    for (int i = 0; i < n; i++) {
      alive[i] = true;
    }
    if (((ll)k * (ll)(k - 1)) / 2LL > (ll)m) {
      cout << "-1\n";
      rese(n);
      continue;
    }
    if (k == 1) {
      cout << "2\n1\n";
      rese(n);
      continue;
    }
    int rem = n;
    vector<int> li;
    bool done = false;
    for (int i = 0; i < n; i++) {
      if (deg[i] <= k - 1) {
        li.push_back(i);
      }
      if (deg[i] == k - 1) {
        if (get_pod(i, k)) {
          done = true;
          break;
        }
      }
    }
    if (done) {
      rese(n);
      continue;
    }
    for (int i = 0; i < li.size() && !done; i++) {
      int now = li[i];
      alive[now] = false;
      for (int j = 0; j < adj[now].size(); j++) {
        int to = adj[now][j];
        deg[to]--;
        if (deg[to] == k - 1) {
          li.push_back(to);
          if (get_pod(to, k)) {
            done = true;
            break;
          }
        }
      }
    }
    if (done) {
      rese(n);
      continue;
    }
    rem = n - (int)(li.size());
    if (rem >= k) {
      cout << "1 " << rem << "\n";
      for (int i = 0; i < n; i++) {
        if (alive[i]) {
          cout << (i + 1) << " ";
        }
      }
      cout << "\n";
      rese(n);
      continue;
    }
    cout << "-1\n";
    rese(n);
  }
}