#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
  #include "debug.hpp"
#else
  #define dbg(...) 0
#endif

template <class T>
void sort_unique(std::vector<T>& v) {
  std::sort(v.begin(), v.end());
  v.resize(std::unique(v.begin(), v.end()) - v.begin());
}

int find_max_clique(const vector<vector<int>>& adj) {
  int n = adj.size();
  vector<vector<int>> q;
  for (int i = 0; i < n; ++i) {
    q.emplace_back(1, i);
  }
  int ans = 0;
  vector<int> cnt(n, 0);
  vector<bool> in_clique(n, false);
  vector<int> goods; goods.reserve(n);
  while (!q.empty()) {
    ans++;
    vector<vector<int>> q2;
    for (const vector<int>& cl0 : q) {
      for (int u : cl0) in_clique[u] = true;
      goods.clear();
      for (int u : cl0) {
        for (int v : adj[u]) if (!in_clique[v]) {
          if (++cnt[v] == ans) {
            goods.push_back(v);
          }
        }
      }
      for (int v : goods) {
        vector<int> cl1 = cl0;
        cl1.push_back(v);
        q2.push_back(cl1);
      }
      for (int u : cl0) {
        for (int v : adj[u]) if (!in_clique[v]) {
          cnt[v]--;
        }
      }
      for (int u : cl0) in_clique[u] = false;
    }
    q2.swap(q);
    sort_unique(q);
  }
  return ans;
}

vector<pair<int, int>> mark_graph(const vector<vector<int>>& adj) {
  int n = adj.size();
  vector<vector<bool>> A(n, vector<bool>(n, false));
  for (int u = 0; u < n; ++u) {
    for (int v : adj[u]) A[u][v] = true;
  }
  vector<array<int, 3>> triplets;
  for (int u = 0; u < n; ++u) {
    for (int v : adj[u]) {
      if (adj[v].size() <= adj[u].size()) {
        for (int w : adj[v]) {
          if (A[u][w]) {
            triplets.push_back({u, v, w});
          }
        }
      }
    }
  }
  sort_unique(triplets);
  vector<int> cnt(n, 0);
  vector<bool> in_cur(n, false);
  pair<int, vector<int>> best_set;
  best_set.first = -1;
  const int K = 5;
  for (const array<int, 3>& triplet : triplets) {
    vector<int> cur; cur.reserve(K);
    for (int i = 0; i < 3; ++i) {
      cur.push_back(triplet[i]);
      in_cur[cur[i]] = true;
    }
    while (int(cur.size()) < K) {
      pair<int, int> best{-1, -1};
      for (int u : cur) {
        for (int v : adj[u]) if (!in_cur[v]) {
          if (++cnt[v] > best.first) {
            best = {cnt[v], v};
          }
        }
      }
      if (best.first < 0) break;
      cur.push_back(best.second);
      in_cur[best.second] = true;
      for (int u : cur) {
        for (int v : adj[u]) if (!in_cur[v]) {
          cnt[v]--;
        }
      }
    }
    for (int u : cur) in_cur[u] = false;
    if (int(cur.size()) < K) continue;
    int n_edges = 0;
    for (int i = 0; i < int(cur.size()); ++i) {
      for (int j = 0; j < i; ++j) {
        n_edges += A[cur[i]][cur[j]];
      }
    }
    if (n_edges > best_set.first) {
      best_set = {n_edges, cur};
    }
  }
  vector<pair<int, int>> ans;
  for (int u : best_set.second) {
    for (int v : best_set.second) if ((v > u) && !A[u][v]) {
      ans.emplace_back(u, v);
    }
  }
  return ans;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> adj(n);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    --u; --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  int max_clique1 = find_max_clique(adj);
  if (max_clique1 >= 5) {
    cout << "ok\n";
  }
  else {
    cout << "mark\n";
    vector<pair<int, int>> ans = mark_graph(adj);
    int k = ans.size();
    cout << k << '\n';
    for (auto [u, v] : ans) {
      cout << (u + 1) << ' ' << (v + 1) << '\n';
    }
  }
}