#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];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m;
    for (ll i = 1;i <= m;i ++){
        ll u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    double average = double(m*2)/n;
    if (sz(g[1])>max(0ll,llround(average-3))){
        cout<<"mark"<<'\n';
        if (sz(g[1])>=5)g[1].resize(5);
        cout<<sz(g[1])<<'\n';
        for (auto x:g[1]){
            cout<<1<<' '<<x<<'\n';
        }
    }
    else{
        cout<<"ok"<<'\n';
    }
}