#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <set>
#include <ranges>
#include <cassert>

using namespace std;

[[noreturn]] void usage()
{
    cerr << "Usage: ./generator seed n m k answer mode [...]" << endl;
    cerr << "answer may be -1 if unknown" << endl;
    exit(1);
}

mt19937 r_dev;
mt19937_64 r_dev64;
// Returns a value in range [0, 1[
double rnd()
{
    return uniform_real_distribution<double>(0, 1)(r_dev);
}
// Returns a value in range [a, b] inclusive
int rnd(int a, int b)
{
    return uniform_int_distribution<int>(a, b)(r_dev);
}
long long rnd64(long long a, long long b)
{
    return uniform_int_distribution<long long>(a, b)(r_dev64);
}
// Returns either 0 or 1
int coin()
{
    return rnd(0, 1);
}
// Shuffles any type with begin and end
template <typename T>
void shuffle(T &&arr)
{
    shuffle(arr.begin(), arr.end(), r_dev);
}

struct Instance {
    int n, m, k;
    vector<pair<int, int>> e;

    void shuffle_labels(int keep_1_n) {
        vector<int> p;
        for (int i = 1; i <= n; ++i) {
            p.push_back(i);
        }
        if (keep_1_n) {
            shuffle(ranges::subrange(p.begin()+1, p.end()-1));
            if (keep_1_n == 2) swap(p[0], p[n-1]);
        } else {
            shuffle(p);
        }
        for (auto &[u, v] : e) {
            u = p[u-1];
            v = p[v-1];
            if (coin()) swap(u, v);
        }
        shuffle(e);
    }

    void print() {
        cout << n << " " << m << " " << k << "\n";
        for (auto [u, v] : e) {
            cout << u << " " << v << "\n";
        }
    }

    vector<vector<int>> components() {
        vector<vector<int>> g(n+1);
        for (auto [u, v] : e) {
            g[u].push_back(v);
            g[v].push_back(u);
        }
        vector<int> z(n+1);
        vector<vector<int>> comps;
        for (int i = 1; i <= n; ++i) {
            if (z[i]) continue;
            z[i] = 1;
            comps.push_back({i});
            auto &q = comps.back();
            for (int qi = 0; qi < (int)q.size(); ++qi) {
                int j = q[qi];
                for (int o : g[j]) if (!z[o]) {
                    z[o] = 1;
                    q.push_back(o);
                }
            }
        }
        return comps;
    }

    vector<int> unused() {
        vector<int> z(n+1);
        for (auto [u, v] : e) z[u] = z[v] = 1;
        vector<int> l;
        for (int i = 1; i <= n; ++i) {
            if (!z[i]) l.push_back(i);
        }
        return l;
    }

    void connect_components_random() {
        auto comps = components();
        shuffle(comps);
        int ncomp = comps.size();
        for (int ci = 1; ci < ncomp; ++ci) {
            int cj = rnd(0, ci-1);
            int i = comps[ci][rnd(0, comps[ci].size()-1)];
            int j = comps[cj][rnd(0, comps[cj].size()-1)];
            assert(i != j);
            e.push_back({i, j});
        }
    }

    void random_augment() {
        set<pair<int, int>> e_set;
        for (auto [u, v] : e) {
            e_set.insert({min(u, v), max(u, v)});
        }
        while ((int)e.size() < m) {
            int u, v;
            do {
                u = rnd(1, n);
                v = rnd(1, n);
                if (u > v) swap(u, v);
            } while (u == v || e_set.count({u, v}));
            e_set.insert({u, v});
            e.push_back({u, v});
        }
    }

    void chain(int start, int end, int length) {
        if (length == 0) {
            assert(start == end);
            return;
        }
        if (length == 1) assert(start != end);
        vector<int> z(n+1);
        for (auto [u, v] : e) z[u] = z[v] = 1;
        z[start] = z[end] = 1;
        vector<int> nodes = {start};
        for (int i = 1; i <= n && (int)nodes.size() < length; ++i) {
            if (!z[i]) nodes.push_back(i);
        }
        assert((int)nodes.size() == length);
        nodes.push_back(end);
        for (int ci = 0; ci+1 < (int)nodes.size(); ++ci) {
            assert(nodes[ci] != nodes[ci+1]);
            e.push_back({nodes[ci], nodes[ci+1]});
        }
    }

    //          /--b--\.
    // 1 --a-- x       y --d-- n
    //          \--c--/
    void eyepatch(int a, int b, int c, int d) {
        assert(b + c > 2);
        int alloc = n;
        int x = a == 0 ? 1 : --alloc;
        int y = d == 0 ? n : --alloc;
        chain(1, x, a);
        chain(x, y, b);
        chain(x, y, c);
        chain(y, n, d);
    }

    //                  /---
    // 1 --a-- n --b-- x   c
    //                  \---
    void lasso(int a, int b, int c) {
        assert(c >= 2);
        int x = b == 0 ? n : n-1;
        chain(1, n, a);
        chain(n, x, b);
        chain(x, x, c);
    }

    vector<int> star(int x, int count=-1) {
        auto nodes = unused();
        if (count == -1) count = nodes.size();
        erase(nodes, x);
        nodes.resize(count);
        assert((int)nodes.size() == count);
        for (int i = 0; i < count; ++i) {
            e.push_back({x, nodes[i]});
        }
        return nodes;
    }
};

int main(int argc, char **argv)
{
    // Check argument count
    if (argc < 7)
        usage();

    // Parse arguments into numbers
    unsigned long long seed = stoull(argv[1]);
    r_dev.seed(seed);
    r_dev64.seed(seed);
    int n = atoi(argv[2]);
    int m = atoi(argv[3]);
    int k = atoi(argv[4]);
    int answer = atoi(argv[5]);
    string mode = argv[6];

    if (mode == "random") {
        Instance inst {n, m, k, {}};
        inst.connect_components_random();
        inst.random_augment();
        inst.shuffle_labels(0);
        inst.print();
    } else if (mode == "chain") {
        int l = atoi(argv[7]);
        Instance inst {n, m, k, {}};
        inst.chain(1, n, l);
        inst.connect_components_random();
        inst.random_augment();
        inst.shuffle_labels(1 + coin());
        inst.print();
    } else if (mode == "eyepatch") {
        int a = atoi(argv[7]);
        int b = atoi(argv[8]);
        int c = atoi(argv[9]);
        int d = atoi(argv[10]);
        Instance inst {n, m, k, {}};
        inst.eyepatch(a, b, c, d);
        inst.connect_components_random();
        inst.random_augment();
        inst.shuffle_labels(1);
        inst.print();
    } else if (mode.starts_with("lasso")) {
        int a = atoi(argv[7]);
        int b = atoi(argv[8]);
        int c = atoi(argv[9]);
        int keep_1_n = atoi(argv[10]);
        Instance inst {n, m, k, {}};
        inst.lasso(a, b, c);
        if (mode == "lasso-star") {
            inst.star(n);
        } else if (mode == "lasso") {
            inst.connect_components_random();
        } else usage();
        inst.random_augment();
        inst.shuffle_labels(keep_1_n);
        inst.print();
    } else if (mode == "star-cycles") {
        int num_cyc = min(m-n+1, (n-1)/3);
        int num_pts = n-1-2*num_cyc;
        Instance inst {n, m, k, {}};
        auto points = inst.star(1, num_pts);
        for (int i = 0; i < num_cyc; ++i) {
            inst.chain(points[i], points[i], 3);
        }
        inst.shuffle_labels(1+coin());
        inst.print();
    } else usage();
}
