#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;
	}
	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;
	}
}

answer.code: In function ‘int main()’:
answer.code:33:17: error: return-statement with no value, in function returning ‘int’ [-fpermissive]
   33 |                 return;
      |                 ^~~~~~
In file included from /usr/include/c++/11/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_algo.h: In instantiation of ‘void std::shuffle(_RAIter, _RAIter, _UGenerator&&) [with _RAIter = int*; _UGenerator = long unsigned int]’:
answer.code:40:9:   required from here
/usr/include/c++/11/bits/stl_algo.h:3750:9: error: ‘std::remove_reference<long unsigned int>::type’ {aka ‘long unsigned int’} is not a class, struct, or union type
 3750 |         __uc_type;
      |         ^~~~~~~~~
/usr/include/c++/11/bits/stl_algo.h:3778:44: error: ‘std::remove_reference<long unsigned int>::type’ {aka ‘long unsigned int’} is not a class, struct, or union type
 3778 |           const pair<__uc_type, __uc_type> __pospos =
      |                                            ^~~~~~~~
/usr/include/c++/11/bits/stl_algo.h:3778:44: error: ‘std::remove_reference<long unsigned int>::type’ {aka ‘long unsigned int’} is not a class, struct, or union type