#include<bits/stdc++.h>
using namespace std;
#define fi first
#define sc second
#define pii pair<int,int>
#define pb push_back
const int maxn=1000+10;
int n,m,f[maxn][maxn],d[maxn],g[maxn][maxn],in[maxn];
mt19937_64 rd(time(0));
int getg(){ 
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=0;
    for(int i=1;i<=n;i++) g[i][i]=1,in[i]=0;
    int rep=m;
    while(rep--){
        int u=rd()%n+1,v=rd()%n+1;
        while(g[u][v]) u=rd()%n+1,v=rd()%n+1;
        g[u][v]=g[v][u]=1,in[u]++,in[v]++;
    }
    int minn=1e9,mincnt=0;
    for(int i=1;i<=n;i++) minn=min(minn,in[i]);
    for(int i=1;i<=n;i++) mincnt+=(minn==in[i]);
//    cout<<mincnt<<endl;
    return mincnt;
}
void solve(){
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++) cin>>u>>v,f[u][v]=f[v][u]=1,d[u]++,d[v]++;
    int s=1e9,rep=50;
    while(rep--) s=min(s,getg());
    int minn=1e9,mini=0;
    for(int i=1;i<=n;i++){
        if(d[i]<minn) minn=d[i],mini=i;
    }
    int cnt=0;
    for(int i=1;i<=n;i++) cnt+=(d[i]==minn);
    for(int i=1;i<=n;i++) minn=min(minn,d[i]);
//    cout<<s<<" "<<cnt<<endl;
    if(minn==0&&cnt>=s+(m<=2500?4:(m<=3500?3:2))) return cout<<"ok"<<endl,void();
    cout<<"mark"<<endl;
    vector<pii> res;
    priority_queue<pii,vector<pii>,greater<pii> > q;
    for(int i=1;i<=n;i++) q.push({d[i],i});
    while(q.size()){
        int u=q.top().sc;
        q.pop();
        for(int i=1;i<=n;i++){
            if(f[i][u]){
                res.pb({i,u});
                if(res.size()==5) break;
            }
        }
        if(res.size()==5) break;
    }
    cout<<res.size()<<endl;
    for(pii p:res) cout<<p.fi<<' '<<p.sc<<endl;
}
int main(){
//	freopen("graph2.in","r",stdin);
//	freopen("graph.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0;
}
/*
Samples
input:

output:

THINGS TODO:
妫€鏌reopen锛屽挨鍏舵槸鍚庣紑鍚?
妫€鏌ョ┖闂?
妫€鏌ヨ皟璇曡鍙ユ槸鍚﹀叏閮ㄦ敞閲?
*/