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:
// Don't place your source in a package
import javax.swing.*;
import java.lang.reflect.Array;
import java.text.DecimalFormat;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
import java.util.stream.Stream;



// Please name your class Main
public class Main {
    static FastScanner fs=new FastScanner();
    static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        public String next() {
            while (!st.hasMoreElements())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
        int Int() {
            return Integer.parseInt(next());
        }

        long Long() {
            return Long.parseLong(next());
        }

        String Str(){
            return next();
        }
    }


    public static void main (String[] args) throws java.lang.Exception {
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        //reading /writing file
        //Scanner sc=new Scanner(new File("input.txt"));
        //PrintWriter pr=new PrintWriter("output.txt");


        int T=Int();
        for(int t=0;t<T;t++){
            int n=Int();
            int m=Int();
            int k=Int();
            int edges[][]=new int[m][2];
            for(int i=0;i<m;i++){
                int a=Int()-1;int b=Int()-1;
                edges[i][0]=a;
                edges[i][1]=b;
            }

            Solution sol=new Solution(out);
            sol.solution(n,k,edges,t+1);
        }
        out.close();

    }

    public static int[] Arr(int n){
        int A[]=new int[n];
        for(int i=0;i<n;i++)A[i]=Int();
        return A;
    }
    public static int Int(){
        return fs.Int();
    }
    public static long Long(){
        return fs.Long();
    }
    public static String Str(){
        return fs.Str();
    }

}








class Solution{
    PrintWriter out;
    int INF=Integer.MAX_VALUE;
    int MOD=1000000007;
    public Solution(PrintWriter out){
        this.out=out;
    }


    public void solution(int n,long k,int edges[][],int t){
        if((k)*(k-1)/2>edges.length){
            out.println(-1);
            return;
        }

        int in[]=new int[n];
        int m=edges.length;
        boolean remove[]=new boolean[n];
        List<Integer>graph[]=new ArrayList[n];
        Set<Integer>gcheck[]=new HashSet[n];
        Arrays.setAll(graph,e->new ArrayList<>());
        Arrays.setAll(gcheck,e->new HashSet<>());


        for(int edge[]:edges){
            int u=edge[0],v=edge[1];
            in[u]++;in[v]++;
            graph[u].add(v);
            graph[v].add(u);
            int mn=Math.min(edge[0],edge[1]);
            int mx=Math.max(edge[0],edge[1]);
            gcheck[mn].add(mx);
        }

        Queue<Integer>q=new LinkedList<>();
        for(int i=0;i<n;i++){
            if(in[i]<=k-1){
                q.add(i);
            }
        }

        //System.out.println(Arrays.toString(in));
        while(q.size()>0){
            int root=q.poll();
            //System.out.println((root+1)+" "+Arrays.toString(in));
            if(in[root]==k-1){
                List<Integer>groups=new ArrayList<>();
                groups.add(root);
                for(int next:graph[root]){
                    if(remove[next])continue;
                    groups.add(next);
                }
                boolean clique =true;
                for(int x=0;x<groups.size();x++){
                    if(!clique)break;
                    int u=groups.get(x);
                    for(int y=x+1;y<groups.size();y++){
                        int v=groups.get(y);
                        int mn=Math.min(u,v);
                        int mx=Math.max(u,v);
                        if(!gcheck[mn].contains(mx)){
                            clique =false;
                            break;
                        }
                    }
                }
                if(clique){
                    out.println(2);
                    for(int j:groups){
                        out.print((j+1)+" ");
                    }
                    out.println();
                    return;
                }
            }

            remove[root]=true;
            for(int next:graph[root]){
                in[next]--;
                if(in[next]==k-1){
                    q.add(next);
                }
            }
            //System.out.println(Arrays.toString(in));
        }


        //jude one
        List<Integer>res=new ArrayList<>();
        for(int i=0;i<n;i++){
            if(in[i]>=k)res.add(i);
        }
        if(res.size()==0){
            out.println(-1);
        }
        else{
            out.println(1+" "+res.size());
            for(int i:res)out.print((i+1)+" ");
            out.println();
        }
    }
}