#include "bits/stdc++.h"
#ifdef DEBUG
#include "algo/debug.hpp"
#else
#define dbg(...)
#define dbgm(...)
#endif
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
// using u128 = __uint128_t;
// using i128 = __int128;
const int mod = 1000000007;
const int N = 1005;
const int LOG = 20;
const int inf = 1e9;
const double eps = 1e-11;
int n, m, k, qq;
int deg[N];
bool adj[N][N];
void solve() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u][v] = adj[v][u] = 1;
        deg[u]++, deg[v]++;
    }
    
    int u = -1, v = -1, cu = 0, cv = 0;
    for (int i = 1; i <= n; i++) {
        if (deg[i] > cv) v = i, cv = deg[i];
        if (cv > cu) swap(u, v), swap(cu, cv);
    }
    
    if (cu - cv >= 5) {
        cout << "ok\n";
        return;
    }
    
    int c = 0;
    cout << "mark\n5\n";
    for (int i = 1; i <= n; i++) {
        if (c == 5) break;
        if (!adj[u][i]) cout << u << " " << i << "\n";
    }
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}