1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>

using namespace std;


int ile_zna[3*1000+1];
int zakleca[3*1000+1][2];

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t,n,m,k,a,b;

    cin>>t;

    vector<int> wyn;

    for(int z=0;z<t;z++){

        cin>>n>>m>>k;
        for(int i=1;i<=n;i++){
            ile_zna[i]=m;
        }
        for(int i=1;i<=m;i++){
            cin>>a>>b;
            ile_zna[a]-=1;
            ile_zna[b]-=1;
            zakleca[i][0]=a;
            zakleca[i][1]=b;
        }

        for(int i=1;i<=n;i++){
            if(ile_zna[i]==0){
                wyn.push_back(i);
            }
        }
        if(wyn.size()>0){
            cout<<1<<" "<<wyn.size()<<endl;
            for(int i=0;i<wyn.size();i++){
                cout<<wyn[i]<<" ";
            }
        }else if(k==1){
            cout<<-1;
        }else{

            for(int i=1;i<=n;i++){
                //cout<<" // ";

                for(int j=1;j<=m;j++){
                    if(zakleca[j][0]!=i && zakleca[j][1]!=i){
                        a=zakleca[j][0];
                        b=zakleca[j][1];
                        break;
                    }
                }

                for(int j=1;j<=m;j++){
                    if(zakleca[j][0]!=i && zakleca[j][1]!=i){
                        if(zakleca[j][0]!=a && zakleca[j][1]!=a){
                            a=0;
                        }
                        if(zakleca[j][0]!=b && zakleca[j][1]!=b){
                            b=0;
                        }
                    }
                }
                //cout<<a<<" "<<b;

                if(a!=0 || b!=0){
                    wyn.push_back(i);
                }

            }
            if(wyn.size()==0){
                cout<<-1;
            }else{
                cout<<2<<" "<<wyn.size()<<endl;
                for(int i=0;i<wyn.size();i++){
                    cout<<wyn[i]<<" ";
                }
            }

        }

        wyn.clear();
        cout<<endl;

    }


}