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
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
#define MULTIPLE_TESTS
// #define ENDLESS_TESTS
#define TIME_LIMIT 1
// #define MEMORY_LIMIT 512

// #define DEBUG_LOG
#define DEBUG_LOG if constexpr (false)

using namespace std;

struct Caster {
    int number;
    int spells;
};

int ceil_div(int a, int b)
{
    return (a + b - 1) / b;
}

void test()
{
    int n, spells, days;
    cin >> n >> spells >> days;

    vector<Caster> casters(n);

    for (int i = 0; i < n; ++i)
    {
        casters[i] = {i+1, spells};
    }

    for (int i = 0; i < spells; ++i)
    {
        int a, b;
        cin >> a >> b;
        casters[a-1].spells -= 1;
        casters[b-1].spells -= 1;
    }

    int min_spells = spells;

    for (auto &caster : casters)
    {
        min_spells = std::min(caster.spells, min_spells);
    }

    DEBUG_LOG { for (auto c : casters) { cout << "(#" << c.number << " = " << c.spells << ") "; } cout << endl; }

    int required_spells = 1;

    for (int day = 1; day <= days; ++day)
    {
        DEBUG_LOG
        {
            cout << "Day #" << day << endl;
            cout << "  Required = " << required_spells << endl;
            cout << "  Lowest = " << min_spells << endl;
        }

        if (min_spells < required_spells)
        {
            DEBUG_LOG cout << "  Run!" << endl;
            const int count = count_if(casters.begin(), casters.end(), [&](const auto &c) { return c.spells < required_spells; });
            cout << day << ' ' << count << '\n';
            for_each(casters.begin(), casters.end(), [&](const auto &c) { if (c.spells < required_spells) cout << c.number << ' '; });
            cout << '\n';
            return;
        }

        if (n == 3) {
            required_spells = spells + 1;
            continue;
        }

        DEBUG_LOG cout << endl;
        required_spells = ceil_div((n-1) * required_spells, n-3);
    }

    cout << "-1\n";
}


int main()
{
#ifndef CONTEST_WORKSPACE
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
#endif

#ifdef ENDLESS_TESTS
    while(!(cin >> std::ws).eof())
        test();
#else
    int T = 0;

#ifdef MULTIPLE_TESTS
    cin >> T;
#else
    T = 1;
#endif

    while (T --> 0)
        test();
#endif

    return 0;
}