#include <bits/stdc++.h>


using namespace std;


#define ff  first
#define ss  second
#define pb  push_back

typedef long long   ll;
typedef pair<ll,ll>  pii;

const int N = 3e5+5;
const int oo = 1e9 - 1;
const int len = oo / 75;

mt19937_64 rng(1);
uniform_int_distribution<int> dis(0, 1000);

int g[1010][1010];
vector <pii> edges;
int deg[1010];

bool cmp (int u, int v) {
  return deg[u] < deg[v];
}

int main(){
  #ifdef LOCAL
  freopen("input.txt","r",stdin);
  #endif // LOCAL
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int n, m; cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int u, v; cin >> u >> v;
    u--;v--;
    deg[u]++;
    deg[v]++;
    edges.pb({u, v});
    g[u][v] = g[v][u] = 1;
  }

  int has = 0;
  for (auto &e1 : edges) {
    for (auto &e2 : edges) {
      int u = e1.ff, v = e1.ss, w = e2.ff, x = e2.ss;
      if (u == v || u == w || u == x || v == w || v == x || w == x) continue;
      if (!g[u][w] || !g[u][x] || !g[v][w] || !g[v][x]) continue;

      vector <int> dgs = {deg[u], deg[v], deg[w], deg[x]};
      sort (dgs.begin(), dgs.end());
      if (dgs[2] > 6) continue;
      has = 1;
    }
  }

  if (has) cout << "ok\n";
  else {
    cout << "mark\n";

    vector <int> ids;
    for (int i = 0; i < n; ++i) ids.pb(i);
    sort (ids.begin(), ids.end(), cmp);
    vector <pii> to_mark;

    int ond = ids[3];
    for (int i = 3; i < n; ++i) {
      if (g[ids[i]][ids[2]]) ond = ids[i];
    }

    vector <int> nds = {ids[0], ids[1], ids[2], ond};
    for (auto &e : nds) {
      for (auto &e2 : nds) {
        if (e == e2) continue;
        if (!g[e][e2]) {
          to_mark.pb({e, e2});
          g[e][e2] = g[e2][e] = 1;
        }
      }
    }

    cout << to_mark.size() << '\n';
    for (auto &e : to_mark) cout << e.ff + 1 << ' ' << e.ss + 1 << '\n';

  }

}