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
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cstdint>
#include <deque>

using namespace std;

typedef vector< vector<bool> > Twiedza;

int medrcow, zaklec, dni;

void utnij_wiedze(Twiedza &wiedza, int m  ){
    for (int i=0; i<medrcow; i++){
        for (int z=0; z<zaklec; z++){
            wiedza[i][z]=wiedza[i][z]&&wiedza[m][z];
        }
    }
}

int ile_wiedzy(const Twiedza & wiedza,  int m ){
    int c=0;
    for (int i=0; i<zaklec;i++)
        c+=wiedza[m][i];
    return c;
}


int wyjdz(Twiedza wiedza, int m, int limit ){
    utnij_wiedze(wiedza,m);

    if (limit==0) return 0;

    if (ile_wiedzy( wiedza ,m)==0) return 1;

    int T = limit-1;

    for (int i=0; i<medrcow; i++){
        if (i!=m){
            T = min(T, wyjdz(wiedza,i,T));
        }
    }
    return T+1;
}


int main(){
    int Q;
    cin>>Q;
    while (Q-->0){

        cin>>medrcow>>zaklec>>dni;

        vector <pair<int, int>> zaklecia;

        for (int i=0; i<zaklec; i++){
            int a,b;
            cin>>a>>b;
            zaklecia.push_back(make_pair(a-1,b-1));
        }

        Twiedza wiedza(medrcow, vector<bool>(zaklec,true));
        for (int i=0; i<zaklec; i++){
            wiedza[zaklecia[i].first][i]=false;
            wiedza[zaklecia[i].second][i]=false;
        }
        int mind=dni+1;
        vector <int> wygnancy;
        for (int m=0; m<medrcow; m++){
            int r=wyjdz( wiedza ,m,mind+1);
            if (r<mind){
                wygnancy.clear();
                wygnancy.push_back(m+1);
                mind=r;
            }else if (r==mind){
                wygnancy.push_back(m+1);
            }
        }
        if (mind<=dni){
            cout<<mind<<" "<<wygnancy.size()<<endl;
            copy(begin(wygnancy), end(wygnancy), ostream_iterator<int>(cout," "));
            cout<<endl;
        }else
            cout<<"-1"<<endl;
    }

    return 0;
}