// Source: https://usaco.guide/general/io

#include <cstdlib>
#include <cstring>
#include <iostream>
#include <utility>
#include <vector>
#include <chrono>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <bitset>
#include <random>

#define int long long
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()

using namespace std;

signed main() {
    cin.tie(0) -> sync_with_stdio(false);

    int N, M; cin >> N >> M;

	vector<int> deg(N, 0);
	vector<set<int>> adj(N);

	for (int i = 0; i < M; i++) {
		int a, b; cin >> a >> b; a--; b--;

		adj[a].insert(b); adj[b].insert(a); deg[a]++; deg[b]++;
	}

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> best;

	for (int i = 0; i < N; i++) {
		pq.push({deg[i], i}); best.push({deg[i], i});
	}

	auto p = best.top(); best.pop();

	if (abs(p.first - best.top().first) >= 4) {
		cout << "ok" << "\n";
		return 0;
	}

	cout << "mark" << "\n";

	cout << 5 << "\n";

	for (int i = 0; i < 5; i++) {
		while (true) {
			auto q = pq.top(); pq.pop();

			if (!adj[p.second].count(q.second)) {
				cout << p.second + 1 << " " << q.second + 1 << "\n";
				adj[p.second].insert(q.second);
				break;
			}
		}
	}
}