#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


int N, M;
bool adj[1010][1010];

void gen(int seed) {
  mt19937_64 rng(seed);
  memset(adj, 0, sizeof(adj));
  for (int i = 0; i < M; ++i) {
    for (; ; ) {
      const int u = rng() % N;
      const int v = rng() % N;
      if (u != v && !adj[u][v]) {
        adj[u][v] = adj[v][u] = true;
        break;
      }
    }
  }
}

void expr() {
  int freq[6 + 1][15 + 1] = {};
  for (int seed = 0; seed < 10'000; ++seed) {
    gen(seed);
    vector<int> deg(N, 0);
    for (int u = 0; u < N; ++u) for (int v = 0; v < N; ++v) if (adj[u][v]) {
      ++deg[u];
    }
    vector<int> us(N);
    for (int u = 0; u < N; ++u) us[u] = u;
    sort(us.begin(), us.end(), [&](int u, int v) -> bool {
      return ((deg[u] != deg[v]) ? (deg[u] > deg[v]) : (u < v));
    });
    /*
    for (int x = 0; x < 6; ++x) {
      printf("%2d ", deg[us[x]]);
      for (int y = 0; y < 6; ++y) {
        printf("%d", adj[us[x]][us[y]]);
      }
      puts("");
    }
    puts("");
    */
    for (int k = 0; k <= 6; ++k) {
      int cnt = 0;
      for (int x = 0; x < k; ++x) for (int y = x + 1; y < k; ++y) if (adj[us[x]][us[y]]) {
        ++cnt;
      }
      ++freq[k][cnt];
    }
  }
  for (int k = 0; k <= 6; ++k) {
    cerr << k << ": "; pv(freq[k], freq[k] + (k*(k-1)/2 + 1));
  }
}
/*
seed \in [0, 10^4)

M = 1500

0: 10000
1: 10000
2: 9672 328
3: 9125 849 26 0
4: 8425 1478 95 2 0 0 0
5: 7619 2136 228 17 0 0 0 0 0 0 0
6: 6726 2745 478 48 3 0 0 0 0 0 0 0 0 0 0 0

M = 5000

0: 10000
1: 10000
2: 9533 467
3: 8717 1229 53 1
4: 7669 2085 236 10 0 0 0
5: 6526 2894 526 51 3 0 0 0 0 0 0
6: 5364 3473 983 161 18 1 0 0 0 0 0 0 0 0 0 0
*/

int main() {
  /*
  N = 1000;
  M = 1500;
  expr();
  M = 5000;
  expr();
  */
  
  scanf("%d%d", &N, &M);
  memset(adj, 0, sizeof(adj));
  for (int i = 0; i < M; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    --u;
    --v;
    adj[u][v] = adj[v][u] = true;
  }
  
  vector<int> deg(N, 0);
  for (int u = 0; u < N; ++u) for (int v = 0; v < N; ++v) if (adj[u][v]) {
    ++deg[u];
  }
  vector<int> us(N);
  for (int u = 0; u < N; ++u) us[u] = u;
  sort(us.begin(), us.end(), [&](int u, int v) -> bool {
    return ((deg[u] != deg[v]) ? (deg[u] > deg[v]) : (u < v));
  });
  int cnt = 0;
  for (int x = 0; x < 5; ++x) for (int y = x + 1; y < 5; ++y) if (adj[us[x]][us[y]]) {
    ++cnt;
  }
  if (cnt >= 5) {
    puts("ok");
  } else {
    vector<pair<int, int>> ans;
    for (int x = 0; x < 5; ++x) for (int y = x + 1; y < 5; ++y) if (!adj[us[x]][us[y]]) {
      ans.emplace_back(us[x], us[y]);
    }
    ans.resize(5);
    puts("mark");
    printf("%d\n", (int)ans.size());
    for (const auto &e : ans) {
      printf("%d %d\n", e.first + 1, e.second + 1);
    }
  }
  
  return 0;
}