#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define all(a) begin(a), end(a)
template<class T> bool chmin(T& a, T b) { if(a <= b) return 0; a = b; return 1; }
template<class T> bool chmax(T& a, T b) { if(a >= b) return 0; a = b; return 1; }


mt19937 rnd(169);
int main() {
//    cin.tie(0)->sync_with_stdio(0);
    
    ll N, M;
    cin >> N >> M;
    
    vector g(N, vector<ll>{});
    rep(i, 0, M) {
        ll A, B;
        cin >> A >> B;
        A--; B--;
        g[A].push_back(B);
        g[B].push_back(A);
    }
    
    vector<ll> deg(N);
    rep(i, 0, N) deg[i] = g[i].size();
    
    vector<ll> hist(100);
    for(ll x : deg) hist[x]++;
    auto p = ranges::max_element(hist);
    
    while(*p > 10) p++;
    
    if(*p == 0) {
        puts("ok");
        return 0;
    }
    
    puts("mark");
    puts("5");
    
    vector<ll> idx;
    cerr << p - begin(hist) << endl;
    rep(i, 0, N) if(g[i].size() >= p - begin(hist)) idx.push_back(i);
    ranges::sort(idx, less<>{}, [&](ll i) { return g[i].size(); });
    for(ll d = 0; idx.size() < 10; d++) {
        rep(i, 0, N) if(idx.size() < 10 and g[i].size() == d) idx.push_back(i);
    }
    idx.resize(10);
    
    auto has_edge = [&](ll i, ll j) -> bool {
        return ranges::count(g[i], j);
    };
    
    auto add_edge = [&](ll i, ll j) -> bool {
        if(i == j) return 0;
        if(ranges::count(g[i], j)) return 0;
        g[i].push_back(j);
        g[j].push_back(i);
        
        cout << i + 1 << ' ' << j + 1 << endl;
        return 1;
    };
    
    ranges::sort(idx);
    for(ll i : idx) cerr << i << " : " << g[i].size() << endl;
    {
        auto [l, r] = ranges::unique(idx);
        assert(l == r);
    }
    while([&] {
        rep(i, 0, 5) if(has_edge(idx[i * 2], idx[i * 2 + 1])) return 1;
        return 0;
    }()) ranges::shuffle(idx, rnd);
    
    rep(i, 0, 5) add_edge(idx[i * 2], idx[i * 2 + 1]);
}