#include<cstdio>
#include<vector>
#include<bitset>
#define M 100005
using namespace std;
struct E{
	int to,nx;
}edge[M<<1];
int tot,head[M];
void Addedge(int a,int b){
	edge[++tot].to=b;
	edge[tot].nx=head[a];
	head[a]=tot;
}
bitset<1005>way[1005];
bool mark[M];
vector<int>S;
int Ans[10][2],sz;
int main(){
//	freopen("002.in","r",stdin);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)way[i].reset();
	while(m--){
		int a,b;
		scanf("%d%d",&a,&b);
		way[a].flip(b);
		way[b].flip(a);
	}
	int x=1,y=2;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)if(way[i][j]){
			Addedge(i,j);
			x=i;y=j;
		}
	}
	bool flag=false;
	for(int now=1;now<=n;now++){
		for(int i=head[now];i;i=edge[i].nx){
			for(int j=head[now];j;j=edge[j].nx){
				if(i==j)continue;
				for(int k=head[now];k;k=edge[k].nx){
					if(i==j||i==k)continue;
					if(!way[edge[j].to][edge[i].to]||!way[edge[j].to][edge[k].to])continue;
					if(!way[edge[i].to][edge[k].to])continue;
					flag=true;
					break;
				}
				if(flag)break;
			}
			if(flag)break;
		}
		if(flag)break;
	}
	if(flag)puts("ok");
	else{
		int cnt=2;
		S.push_back(x);
		S.push_back(y);
		mark[x]=mark[y]=true;
		for(int i=1;i<=n;i++){
			if(mark[i])continue;
			cnt++;
			mark[i]=true;
			S.push_back(i);
			if(cnt==4)break;
		}
		for(int i=0;i<(int)S.size();i++){
			for(int j=i+1;j<(int)S.size();j++){
				if(!way[S[i]][S[j]]){
					way[S[i]][S[j]]=way[S[j]][S[i]]=1;
					sz++;
					Ans[sz][0]=S[i];
					Ans[sz][1]=S[j];
				}
			}
		}
		puts("mark");
		for(int i=1;i<=sz;i++)printf("%d %d\n",Ans[i][0],Ans[i][1]);
	}
	return 0;
}