#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random(ll l,ll r){
    return rng()%(r-l+1)+l;
}
ll myrandom(ll i){
    return rng()%i;
}
ll n,m;
vector <ll> g[1010];
const ll MOD = 1e9 + 7;
ll p(ll x,ll y){
    ll res = 1;
    for (;y;y>>=1,x*x%MOD){
        if (y&1)res = res*x%MOD;
    }
    return res;
}
ll f(ll x,ll y){
    if (x>y)swap(x,y);
    return p(2,x*(n*1)+y);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m;
    vector <pll> edge;
    ll sum = 0;
    for (ll i = 1;i <= m;i ++){
        ll u,v;
        cin>>u>>v;
        sum ^= f(u,v);
    }
    if (sum <= 100){
        cout<<"ok"<<endl;
    }
    else{
        cout<<"mark"<<endl;
        vector <pll> ans;
        while (1){
            vector <pll> cur;
            for (ll i = 0;i < 5;i++){
                ll u,v;
                u = random(1,n),v = random(1,n);
                while (u==v)u = random(1,n),v = random(1,n);
                cur.push_back({u,v});
            }
            for (auto x:cur)sum^=f(x.fi,x.se);
            if (sum <= 100){
                ans = cur;
                break;
            }
            for (auto x:cur)sum^=f(x.fi,x.se);
        }
        cout<<sz(ans)<<'\n';
        for (auto x:ans)cout<<x.fi<<' '<<x.se<<'\n';;
    }
//    cout<<even<<'\n';
}