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 JAVA):

Solution:
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import java.util.*;
import java.io.*;
import java.math.*;

   public class x1439B
   {
      static HashSet<Integer>[] edges;
      public static void main(String hi[]) throws Exception
      {
         FastScanner infile = new FastScanner();
         int T = infile.nextInt();
         StringBuilder sb = new StringBuilder();
         matcha:while(T-->0)
         {
            int N = infile.nextInt();
            int M = infile.nextInt();
            int K = infile.nextInt();
            edges = new HashSet[N+1];
            for(int i=1; i <= N; i++)
               edges[i] = new HashSet<Integer>();
            for(int i=0; i < M; i++)
            {
               int a = infile.nextInt();
               int b = infile.nextInt();
               edges[a].add(b);  edges[b].add(a);
            }
            TreeSet<Integer> bst = new TreeSet<Integer>((x,y) -> {
               if(edges[x].size() == edges[y].size())
                  return x-y;
               return edges[x].size()-edges[y].size();
            });
            for(int v=1; v <= N; v++)
               bst.add(v);
            while(bst.size() > 0)
            {
               int curr = bst.first();
               if(edges[curr].size() >= K)
               {
                  ArrayList<Integer> group = new ArrayList<Integer>();
                  for(int v=1; v <= N; v++)
                     if(edges[v].size() >= K)
                        group.add(v);
                  sb.append("1 "+group.size()+"\n");
                  for(int v: group)
                     sb.append(v+" ");
                  sb.append("\n");
                  continue matcha;
               }
               else if(edges[curr].size() == K-1)
               {
                  ArrayList<Integer> clique = new ArrayList<Integer>();
                  clique.add(curr);
                  for(int next: edges[curr])
                     clique.add(next);
                  boolean works = true;
                  lol:for(int i=0; i < clique.size(); i++)
                     for(int j=i+1; j < clique.size(); j++)
                        if(!edges[clique.get(i)].contains(clique.get(j)))
                        {
                           works = false;
                           break lol;
                        }
                  if(works)
                  {
                     sb.append("2\n");
                     for(int v: edges[curr])
                        sb.append(v+" ");
                     sb.append(curr+"\n");
                     continue matcha;
                  }
               }
               bst.remove(curr);
               for(int next: edges[curr])
               {
                  bst.remove(next);
                  edges[next].remove(curr);
                  bst.add(next);
               }
            }
            sb.append("-1\n");
         }
         System.out.print(sb);
      }
   }
   class FastScanner 
   {
        private int BS = 1 << 16;
        private char NC = (char) 0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;
 
        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }
 
        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            } catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }
 
        private char getChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }
 
        public int nextInt() {
            return (int) nextLong();
        }
 
        public int[] nextInts(int N) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong();
            }
            return res;
        }
 
        public long[] nextLongs(int N) {
            long[] res = new long[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextLong();
            }
            return res;
        }
 
        public long nextLong() {
            cnt = 1;
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = getChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                cnt *= 10;
            }
            return neg ? -res : res;
        }
 
        public double nextDouble() {
            double cur = nextLong();
            return c != '.' ? cur : cur + nextLong() / cnt;
        }
 
        public double[] nextDoubles(int N) {
            double[] res = new double[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextDouble();
            }
            return res;
        }
 
        public String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c > 32) {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }
 
        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c != '\n') {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }
 
        public boolean hasNext() {
            if (c > 32) return true;
            while (true) {
                c = getChar();
                if (c == NC) return false;
                else if (c > 32) return true;
            }
        }
   }