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
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;

bool czyWspolne(const vector<vector<int> >& zaklecia, const int& n, const int&m) {
    bool check=true;
    int tmpZ=m-zaklecia[n].size();
    unordered_set<int> tmp;
    for (int i = 0; i < zaklecia[n].size(); i++) tmp.insert(zaklecia[n][i]);
    for (int i = 0; i < zaklecia.size(); i++) {
        if (i == n) continue;
        int tmpZ1 = tmpZ;
        for (int j = 0; j < zaklecia[i].size(); j++) {
            if (tmp.find(zaklecia[i][j])!=tmp.end()){ 
                tmpZ1--;
            }
        }
        if (tmpZ1 < 1) return false;
    }
    return check;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int z = 0; z < n; z++) {
        int n, m, k;
        cin >> n >> m >> k;
        vector<vector<int> > zaklecia;
        zaklecia.resize(n);
        for (int y = 0; y < m; y++) {
            int a, b;
            cin >> a >> b;
            zaklecia[a-1].push_back(y);
            zaklecia[b-1].push_back(y);
        }
        int dzien = 1;
        queue<int> kol;
        for (int i = 0; i < n; i++) {
            if (zaklecia[i].size() == m) kol.push(i);
        }
        while (kol.empty()&&dzien<k){
            for (int i = 0; i < n; i++) {
                if (!czyWspolne(zaklecia, i, m)) kol.push(i);
            }
            dzien++;
        }
        
        if (kol.empty()) cout << -1 << "\n";
        else {
            cout << dzien << " " << kol.size() << "\n";
            while (!kol.empty()) {
                cout << kol.front()+1 << " ";
                kol.pop();
            }
            cout << "\n";
        }
    }
}