#include<bits/stdc++.h>
using namespace std;
const int N=5e3+100;
int n,m;
vector<int>g[N];
int vis[N],a[N][N];
int check(vector<int>&st)
{
	int tot=0;
	for(int i=0;i<st.size();i++)for(int j=i+1;j<st.size();j++)if(a[st[i]][st[j]])tot++;
	return tot;
}
void dfs(int x,vector<int>st)
{
	st.push_back(x);vis[x]=1;
	if(check(st)!=st.size()*(st.size()-1)/2)return;
	if(st.size()==5){cout<<"ok"<<endl;exit(0);}
	for(auto y:g[x])if(!vis[y])dfs(y,st);
	st.pop_back();vis[x]=0;
}
signed main()
{
	cin>>n>>m;for(int i=1,x,y;i<=m;i++)cin>>x>>y,g[x].push_back(y),g[y].push_back(x),a[x][y]=a[y][x]=1;
	for(int i=1;i<=n;i++)dfs(i,vector<int>{});
	memset(vis,0,sizeof(vis));
	uniform_int_distribution<int>dist(1,n);mt19937 rd(time(0));
	while(1)
	{
		vector<int>p;
		for(int i=1;i<=5;i++)
		{
			int x;while((x=dist(rd))&&vis[x]);
			vis[x]=1;p.push_back(x);
		}
		if(check(p)>=5)
		{
			cout<<"mark"<<endl<<10-check(p)<<endl;
			for(int i=0;i<p.size();i++)for(int j=i+1;j<p.size();j++)if(!a[p[i]][p[j]])
				cout<<p[i]<<' '<<p[j]<<endl;
			exit(0);
		}
		for(auto x:p)vis[x]=0;
	}
	return 0;
}