#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(1);
ll random(ll l,ll r){
    return rng()%(r-l+1)+l;
}
ll myrandom(ll i){
    return rng()%i;
}
ll n,m;
ll val[1010][1010];
struct graph{
    set <pll> s;
    void add_edge(ll u,ll v){
        if (u > v)swap(u,v);
        if (s.find({u,v})==s.end())s.insert({u,v});
        else s.erase({u,v});
    }
    ll cnt[1010];
    ll eval(){
        memset(cnt,0,sizeof cnt);
        for (auto x:s)cnt[x.fi]++,cnt[x.se]++;
        ll res = 0;
        for (auto x:s){
            res ^= val[cnt[x.fi]][cnt[x.fi]];
        }
        return res;
    }
};
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    for (ll i = 1;i <= 1000;i ++){
        for (ll j = 1;j <= 1000;j ++){
            val[i][j] = random(0,1023);
        }
    }
    cin>>n>>m;
    graph g;
    for (ll i = 1;i <= m;i ++){
        ll u,v;
        cin>>u>>v;
        g.add_edge(u,v);
    }
    if (g.eval() == 69){
        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});
            }
            graph tmp = g;
            for (auto x:cur){
                tmp.add_edge(x.fi,x.se);
            }
            if (tmp.eval()==69){
                ans = cur;
                break;
            }
        }
        cout<<sz(ans)<<'\n';
        for (auto x:ans)cout<<x.fi<<' '<<x.se<<'\n';;
    }
//    cout<<even<<'\n';
}