#include "cseslib.hpp"
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

void failmsg(string msg="") {
    if (msg != "") cerr << msg << endl;
    fail();
}

int main() {
    auto nmk = read_ints(3, 1, 2e6);
    int n = nmk[0];
    int m = nmk[1];
    int k_ = nmk[2];
    if (n < 2 || n > 2e5) failmsg("n out of bounds");
    if (m < n-1 || m > n+10) failmsg("m out of bounds");
    if (k < 1 || k > 1e4) failmsg("k out of bounds");

    vector<vector<int>> e(n+1);
    set<pair<int, int>> e_set;
    for (int i = 0; i < m; ++i) {
        auto uv = read_ints(2, 1, n);
        int u = uv[0];
        int v = uv[1];
        if (u > v) swap(u, v);
        if (u == v) failmsg("self-loop");
        if (e_set.count({u, v})) failmsg("duplicate edge");
        e_set.insert({u, v});
        e[u].push_back(v);
        e[v].push_back(u);
    }

    // Connected
    vector<int> z(n+1);
    z[1] = 1;
    vector<int> q{1};
    for (int qi = 0; qi < (int)q.size(); ++qi) {
        int i = q[qi];
        for (int j : e[i]) {
            if (!z[j]) {
                z[j] = 1;
                q.push_back(j);
            }
        }
    }
    if ((int)q.size() != n) failmsg("graph not connected");

    vector<int> g;
    if (n <= 10 && k_ <= 10) g.push_back(1);
    if (n <= 100 && k_ <= 100) g.push_back(2);
    if (m == n-1) g.push_back(3);
    if (m == n-1 || m == n) g.push_back(4);
    if (n <= 1000) g.push_back(5);
    g.push_back(6);

    end_groups(g);
}
