#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))
ll n,m;
vector <ll> g[1010];
const ll check = 100;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m;
    vector <pll> edge;
    for (ll i = 1;i <= m;i ++){
        ll u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
        edge.push_back({u,v});
    }
    ll cnt[check]={};
    for (ll i = 1;i <= n;i ++){
        if (sz(g[i])<check)cnt[sz(g[i])]^=1;
    }
    ll sum = 0;
    for (ll i = 0;i < check;i ++)sum += cnt[i];
    if (sum>3){
        cout<<"mark\n";
        vector <pll> del;
        for (ll i = 0;i < 5;i ++){
            ll best = sum;
            pll nw = {0,0};
            for (ll j = 1;j <= n;j ++){
                for (auto x:g[j]){
                    vector <ll> dif({sz(g[j]),sz(g[j])-1,sz(g[x]),sz(g[x])-1});
                    for (auto y:dif){
                        sum -= cnt[y];
                        cnt[y]^=1;
                        sum += cnt[y];
                    }
                    if (sum < best){
                        best = sum;
                        nw = {j,x};
                    }
                    for (auto y:dif){
                        sum -= cnt[y];
                        cnt[y]^=1;
                        sum += cnt[y];
                    }
                }
            }
            if (nw.fi != 0){
                ll j,x;
                j = nw.fi,x=nw.se;
                del.push_back({j,x});
                vector <ll> dif({sz(g[j]),sz(g[j])-1,sz(g[x]),sz(g[x])-1});
                for (auto y:dif){
                    sum -= cnt[y];
                    cnt[y]^=1;
                    sum += cnt[y];
                }
                for (ll k = 0;k < sz(g[j]);k++){
                    if (g[j][k]==x){
                        g[j].erase(g[j].begin()+k);
                    }
                }
                for (ll k = 0;k < sz(g[x]);k++){
                    if (g[x][k]==j){
                        g[x].erase(g[x].begin()+k);
                    }
                }

            }
        }
        cout<<sum<<'\n';
        cout<<sz(del)<<'\n';
        for (auto x:del)cout<<x.fi<<' '<<x.se<<'\n';
    }
    else{
        cout<<"ok";
    }
//    cout<<even<<'\n';
}