#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(157);
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();
    ranges::sort(deg);
    deg.resize(10);
    
    rep(i, 0, 10) cerr << deg[i] << " \n"[i == 9];
    
    ll lo = 1125, hi = 1500
    ll ans = -(lo + hi) / 2;
    rep(_, 0, 30000) {
        vector<ll> d(N);
        rep(m, 0, M * 2) d[rnd() % N]++;
        
        vector<ll> cnt(M * 2 + 1);
        for(ll x : d) cnt[x]++;
        
        vector<ll> A, B;
        [&]{
            rep(i, 0, M * 2 + 1) rep(_, 0, cnt[i]) {
                A.push_back(i);
                if(A.size() == 10) return;
            }
        }();
        
        if(deg <= A) {
            ans++;
            continue;
        }
        
        [&]{
            ll c = 10;
            rep(i, 0, M * 2 + 1) rep(_, 0, cnt[i]) {
                if(c) {
                    c--;
                    cnt[i + 1]++;
                }
                else {
                    B.push_back(i);
                    if(B.size() == 10) return;
                }
            }
        }();
        
        if(B <= deg) ans--;
    }
    
    cerr << ans << endl;
    
    if(ans < 0) {
        puts("ok");
        return 0;
    }
    
    puts("mark");
    puts("5");
    vector<ll> idx(N);
    rep(i, 0, N) idx[i] = i;
    
    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;
    };
    
    rep(_, 0, 5) {
        ranges::shuffle(idx, rnd);
        ranges::sort(idx, less<>{}, [&](ll i) { return g[i].size(); });
        rep(j, 1, N) if(add_edge(idx[0], idx[j])) break;
    }
}

answer.code: In function ‘int main()’:
answer.code:35:5: error: expected ‘,’ or ‘;’ before ‘ll’
   35 |     ll ans = -(lo + hi) / 2;
      |     ^~
answer.code:52:13: error: ‘ans’ was not declared in this scope; did you mean ‘abs’?
   52 |             ans++;
      |             ^~~
      |             abs
answer.code:70:22: error: ‘ans’ was not declared in this scope; did you mean ‘abs’?
   70 |         if(B <= deg) ans--;
      |                      ^~~
      |                      abs
answer.code:73:13: error: ‘ans’ was not declared in this scope; did you mean ‘abs’?
   73 |     cerr << ans << endl;
      |             ^~~
      |             abs