#include "testlib.h"
//#include "jngen.h"
#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int INF = 1e9;

vector<int> p;
vector<vector<char>> g;
vector<pair<int, int>> edges;

vector<char> used, sv;

int getp(int a){
    return a == p[a] ? a : p[a] = getp(p[a]);
}

bool unite(int a, int b){
    a = getp(a), b = getp(b);
    if (a == b) return false;
    p[b] = a;
    return true;
}

int calc(int n){
    iota(p.begin(), p.end(), 0);
    int cnt = n;
    g.assign(n, vector<char>(n, 0));
    forn(i, edges.size()) if (used[i]){
        int v = edges[i].first, u = edges[i].second;
        g[v][u] = g[u][v] = 1;
        cnt -= unite(v, u);
    }
    if (cnt != 1) return INF;
    vector<vector<int>> dp(1 << n, vector<int>(n));
    forn(s, n) dp[1 << s][s] = 1;
    forn(mask, 1 << n){
        forn(v, n) if (dp[mask][v]){
            forn(u, n) if (!((mask >> u) & 1) && g[v][u]){
                dp[mask | (1 << u)][u] = min(INF, dp[mask | (1 << u)][u] + dp[mask][v]);
            }
        }
    }
    int tot = 0;
    forn(i, n) tot = min(INF, tot + dp[(1 << n) - 1][i]);
    return tot;
}

void dump(int n, int m, int k, int val){
    string name = "tests/" + to_string(val) + "_" + to_string(rnd.next(INF)) + ".in";
    freopen(name.c_str(), "w", stdout);
    printf("%d %d %d\n", n, m, k);
    forn(i, edges.size()) if (sv[i]){
        int v = edges[i].first, u = edges[i].second;
        if (rnd.next(2)) swap(v, u);
        printf("%d %d\n", v + 1, u + 1);
    }
    puts("");
    fclose(stdout);
}

int main(int argc, char* argv[]) {
    registerGen(argc, argv, 1);
    int n = atoi(argv[1]);
    int m = atoi(argv[2]);
    int k = atoi(argv[3]);
    double t0 = atof(argv[4]);
    double chg = atof(argv[5]);

    forn(i, n) forn(j, i) edges.push_back({i, j});
    shuffle(edges.begin(), edges.end());
    p.resize(n);

    used.assign(edges.size(), 0);
    forn(i, m) used[i] = 1;
    sv = used;
    int ans = calc(n);
    int ans_iter = 0;

    int iter = 0;
    while (ans > 0){
        ++iter;
        double temp = t0;
        used = sv;
        int cur = calc(n);
        while (temp / t0 >= 1.0 / edges.size()){
            vector<char> was = used;
            vector<vector<int>> p(2);
            forn(i, edges.size())
                p[used[i]].push_back(i);
            forn(i, 2)
                shuffle(p[i].begin(), p[i].end());
            for (int it = 0; it < min(p[0].size(), p[1].size()) * temp / t0 && it < int(min(p[0].size(), p[1].size())); it++)
                swap(p[0][it], p[1][it]);
            forn(i, 2) for (int x : p[i])
                used[x] = i;
            int tmp = calc(n);
            if (ans > tmp || (ans == tmp && ans_iter != iter)){
                ans = tmp;
                ans_iter = iter;
                sv = used;
                cerr << ans << " " << (temp / t0) << endl;
                dump(n, m, k, ans);
            }
            if (tmp < cur){
                cur = tmp;
            }
            else{
                double t = exp((cur - tmp) / temp);
                int x = 1 + rand();
                int y = 1 + rand();
                x %= y;
                if (x / (double) y <= t)
                    cur = tmp;
                else
                    used = was;
            }
            temp *= chg;
        }
    }
}