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

const int maxn = 1e3+5;

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

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    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() >= m*2/n + 8*m/2000)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;
        }
    }
}