#include <bits/stdc++.h>

using namespace std;

typedef long double ldb;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned int u32;
typedef pair<int, int> pii;

// std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
// priority_queue<int, vector<int>, greater<int>> minq;
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// fflush(stdout);

const int inf = 1000000007;
const i64 prm = 998244353;
const i64 inf2 = ((i64)inf) * inf;
const int maxn = 1100010; // 1.1e6

inline int read(){
  int x=0,f=0; char ch=getchar();
  while(!isdigit(ch)) f|=(ch==45),ch=getchar();
  while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
  return f?-x:x;
}

int main() {
  int n = read(), m = read();
  set<pii> S;
  static int cnt[1010];
  for (int i = 0; i < m; ++i) {
    int u = read(), v = read();
    S.insert(pii{u, v});
    S.insert(pii{v, u});
    cnt[u]++;
    cnt[v]++;
  }
  vector<pii> vt;
  for (int i = 1; i <= n; ++i) {
    vt.emplace_back(cnt[i], i);
  }
  sort(vt.begin(), vt.end());
  auto ok = [&]() {
    if (vt[994].first == vt[993].first) {
      return false;
    }
    vector<int> p;
    for (int i = 0; i < 6; ++i) p.push_back(vt[i+994].second);
    sort(p.begin(), p.end());
    do {
      auto check = [&]() {
        for (int i = 0; i < 5; ++i) {
          pii e{p[i], p[i+1]};
          if (S.find(e) == S.end()) {
            return false;
          }
        }
        return true;
      };
      if (check()) {
        return true;
      }
    } while (next_permutation(p.begin(), p.end()));
    return false;
  };
  if (ok()) {
    puts("ok");
    return 0;
  }

  vector<int> p;
  for (int i = 0; i < 6; ++i) p.push_back(vt[i+994].second);
  sort(p.begin(), p.end());
  do {
    auto check = [&]() {
      for (int i = 0; i < 5; ++i) {
        pii e{p[i], p[i+1]};
        if (S.find(e) != S.end()) {
          return false;
        }
      }
      return true;
    };
    if (check()) {
      break;
    }
  } while (next_permutation(p.begin(), p.end()));

  puts("mark");
  cout << 5 << endl;
  /*
  cout << 1000 << " " << 5+S.size()/2 << endl;
  for (auto e: S)if (e.first < e.second) printf("%d %d\n", e.first, e.second);
  */
  for (int i = 0; i < 5; ++i) {
    pii e{p[i], p[i+1]};
    assert(S.find(e) == S.end());
    printf("%d %d\n", p[i], p[i+1]);
  }

  return 0;
}