#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];

void gen_random(int n, int m, float& t_max){
    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});
    }
    t_max += *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;
    }
}

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);
    }
    if(m <= 4000){
        float total = 0;
        for(int test = 0; test < 2000; test++)gen_random(n, m, total);
        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 + 3)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;
            }
        }
    }
    else {
        int mn = 1;
        for(int i = 1; i <= n; i++){
            if(g[i].size() < g[mn].size())mn = i;
        }
        if(g[mn].empty())cout << "ok";
        else{
            cout << "mark\n";
            cout << g[mn].size() << "\n";
            for(auto v: g[mn])cout << mn << " " << v << "\n";
        }
    }
}