#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll mod = 1e9 + 7;
// cope counter = 2254

int adj[1001][1001], cnt[1001];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	int u, v;
	for(int i = 0; i < m; i++) {
		cin >> u >> v;
		u--, v--;
		cnt[u]++, cnt[v]++;
		adj[u][v] = adj[v][u] = 1;
	}
	cnt[n] = 0;
	u = v = n;
	for(int i = 0; i < n; i++) {
		if(cnt[i] > cnt[v]) v = i;
		if(cnt[v] > cnt[u]) swap(u, v);
	}
	if(cnt[u] - cnt[v] > 4) {
		cout << "ok\n";
		return 0;
	}
	v = 0;
	cout << "mark\n5\n";
	int arr[n];
	for(int i = 0; i < n; i++) arr[i] = i;
	mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
	shuffle(arr, arr + n, rng);
	for(int i = 0; i < n; i++) {
		if(!adj[u][arr[i]]) {
			v++;
			cout << u << " " << arr[i] << "\n";
		}
		if(v == 5) break;
	}
}