/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;

// https://i11www.iti.kit.edu/extra/publications/sw-fclt-05_t.pdf
// O(n + m * sqrt(m)) process() calls for graphs without loop or multiedges
void find_3_cycles(int n, const vector<array<int, 2>> &edge, auto process){
    int m = (int)edge.size();
    vector<int> deg(n), order, pos(n);
    vector<vector<int>> appear(m + 1), adj(n), found(n);
    for(auto [u, v]: edge) ++ deg[u], ++ deg[v];
    for(auto u = 0; u < n; ++ u) appear[deg[u]].push_back(u);
    for(auto d = m; d >= 0; -- d) order.insert(order.end(), appear[d].begin(), appear[d].end());
    for(auto i = 0; i < n; ++ i) pos[order[i]] = i;
    for(auto i = 0; i < m; ++ i){
        int u = pos[edge[i][0]], v = pos[edge[i][1]];
        adj[u].push_back(v), adj[v].push_back(u);
    }
    for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) if(u < v){
        for(auto i = 0, j = 0; i < (int)found[u].size() && j < (int)found[v].size(); ){
            if(found[u][i] == found[v][j]){
                process(order[u], order[v], order[found[u][i]]);
                ++ i, ++ j;
            }
            else if(found[u][i] < found[v][j]) ++ i;
            else ++ j;
        }
        found[v].push_back(u);
    }
}

template<bool Enable_small_to_large = true>
struct disjoint_set{
    int n, _classes;
    vector<int> p;
    disjoint_set(int n): n(n), _classes(n), p(n, -1){ }
    int make_set(){
        p.push_back(-1);
        ++ _classes;
        return n ++;
    }
    int classes() const{
        return _classes;
    }
    int root(int u){
        return p[u] < 0 ? u : p[u] = root(p[u]);
    }
    bool share(int a, int b){
        return root(a) == root(b);
    }
    int size(int u){
        return -p[root(u)];
    }
    bool merge(int u, int v){
        u = root(u), v = root(v);
        if(u == v) return false;
        -- _classes;
        if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v);
        p[u] += p[v], p[v] = u;
        return true;
    }
    bool merge(int u, int v, auto act){
        u = root(u), v = root(v);
        if(u == v) return false;
        -- _classes;
        bool swapped = false;
        if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v), swapped = true;
        p[u] += p[v], p[v] = u;
        act(u, v, swapped);
        return true;
    }
    void clear(){
        _classes = n;
        fill(p.begin(), p.end(), -1);
    }
    vector<vector<int>> group_up(){
        vector<vector<int>> g(n);
        for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i);
        g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end());
        return g;
    }
};

int n, m;
vector<array<int, 2>> G;
map<int, int> adj[1005];
int indeg[1005], av[1005];

void add_edge(int u, int v) {
    ++indeg[u], ++indeg[v];
    adj[u][v]++, adj[v][u]++;
}

bool check(vector<int> &pos) {
    for (int i = 0; i < isz(pos); ++i) {
        for (int j = i + 1; j < isz(pos); ++j) {
            if (adj[pos[i]].find(pos[j]) == adj[pos[i]].end())
                return true;
        }
    }
    return false;
}

void solve() {
    cin >> n >> m;
    disjoint_set dsu(n);
    iota(av + 1, av + n + 1, 1);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        // dsu.merge(u, v);
        // G.push_back({u, v});
    }
    sort(av + 1, av + n + 1, [&](int x, int y) {
        return indeg[x] > indeg[y];
    });
    int cnt = 0;
    vector<int> pos;
    vector<pair<int, int>> op;
    for (int i = 1; i <= 8; ++i) if (indeg[av[i]] % 2) {
        pos.emplace_back(av[i]);
    }
    while (isz(pos) > 1 and check(pos)) {
        int woo1 = -1, woo2 = -1;
        for (int i = 0; i < isz(pos); ++i)
            for (int j = i + 1; j < isz(pos); ++j)
                if (adj[pos[i]].find(pos[j]) == adj[pos[i]].end())
                    woo1 = i, woo2 = j;
        add_edge(pos[woo1], pos[woo2]);
        op.emplace_back(pos[woo1], pos[woo2]);
        vector<int> npos;
        for (int i = 0; i < isz(pos); ++i) if (i != woo1 and i != woo2) npos.emplace_back(pos[i]);
        pos = npos;
    }
    for (int idx : pos) {
        for (int j = n; j >= 1; --j) if (adj[idx].find(av[j]) == adj[idx].end()) {
            add_edge(av[j], idx);
            op.emplace_back(av[j], idx);
            break;
        }
    }
    if (isz(op) == 0) {
        cout << "ok" << endl;
        return;
    }
    cout << "mark" << endl << isz(op) << endl;
    for (auto [u, v] : op) cout << u << " " << v << endl;
    // for (int i = 0; i < 10; ++i) cout << indeg[av[i + 1]] << " \n"[i == 9];
    // assert(*max_element(indeg, indeg + n) <= 5);
    // cout << dsu.classes() << endl;
    // find_3_cycles(n, G, process);
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
   cout << "Check array size pls sir" << endl;
#endif

}