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

const int maxn = 1e3+5;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<int> g[maxn];
int used[maxn];

int edg[maxn][maxn];
int d[maxn];

int gen_random(int n, int m){
    vector<pair<int, int>> edges;
    for(int i = 0; i < m; i++){
        int a = rng()%n + 1, b = rng()%n + 1;
        while(edg[a][b])b = rng()%n + 1;
        d[a]++;
        d[b]++;
        edg[a][b] = 1;
        edg[b][a] = 1;
        edges.push_back({a, b});
    }
    int res = *max_element(d+1, d+n+1);
    for(auto v: edges){
        d[v.first]--;
        d[v.second]--;
        edg[v.first][v.second] = 0;
        edg[v.second][v.first] = 0;
    }
    return res;
}

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)edg[i][i] = 1;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    float total = 0;
    for(int test = 0; test < 2000; test++)total += gen_random(n, m);
    total /= 2000;
    int mn = 1;
    for(int i = 1; i <= n; i++){
        if(g[i].size() > g[mn].size())mn = i;
    }
    // cout << mn << " " << g[mn].size() << endl;
    if(g[mn].size() >= total + 2.5)cout << "ok";
    else{
        cout << "mark\n";
        cout << "5\n";
        int cnt = 0;
        for(auto v: g[mn])used[v] = 1;
        for(int i = 1; i <= n; i++){
            if(used[i] || i == mn)continue;
            cout << mn << " " << i << "\n";
            cnt++;
            if(cnt == 5)return 0;
        }
    }
}