#include <bits/stdc++.h>
using namespace std;

const int N = 1050;
const int LAMBDA = 8000;

int n, m;
vector<int> e[N];
int f[N];
int Find(int x) { return x == f[x] ? x : f[x] = Find(f[x]); }

bool is_con(int u, int v) {
    int fu = Find(u), fv = Find(v);
    return fu == fv;
}

void connect(int u, int v) {
    int fu = Find(u), fv = Find(v);
    if (fu != fv)
        f[fv] = fu;
}
using pii = pair<int, int>;

void work_mark() {
    for (int i = 1; i <= n; i++)
        f[i] = i;

    for (int i = 1; i <= n; i++)
        for (auto v : e[i])
            connect(i, v);

    sort(e + 1, e + n + 1, [](auto x, auto y) {
        return x.size() < y.size();
    });

    int cnt = 5;
    vector<pii> vec;
    for (int i = 1; i <= n; i++) {
        for (auto v : e[i]) {
            cnt--;
            vec.push_back({i, v});
            if (cnt == 0)
                break;
        }
        if (cnt == 0)
            break;
    }

    cout << "mark\n";
    cout << vec.size() << "\n";
    for (auto [u, v] : vec) {
        cout << u << " " << v << "\n";
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
    }

    int isolate = 0;
    for (int i = 1; i <= n; i++) {
        if (e[i].size() == 0)
            isolate++;
    }

    // cerr << "isolate: " << isolate << endl;
    if (isolate * m > LAMBDA) {
        cout << "ok" << endl;
        return 0;
    }

    work_mark();

    return 0;
}