#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

mt19937 rnd(234);
const ll inf = 1e18;

#include "seq.h"

vector<int> swp(int a, int b) {
    vector<int> rs;
    int s = a + b;
    vector<int> usd(s + 1, 0);
    usd[a] = true;
    queue<int> q;
    vector<pair<int, int>> pr(s + 1);
    q.push(a);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        int y = s - x;
        if (x % 2 == 0 && !usd[x / 2]) {
            usd[x / 2] = true;
            q.push(x / 2);
            pr[x / 2] = make_pair(x, 0);
        }
        if (y % 2 == 0 && !usd[s - (y / 2)]) {
            usd[s - y / 2] = true;
            q.push(s - (y / 2));
            pr[s - (y / 2)] = make_pair(x, 1);
        }
		if(usd[b]){
			break;
		}
    }
    if (usd[b]) {
        int t = b;
        while (t != a) {
            rs.push_back(pr[t].second);
            t = pr[t].first;
        }
        reverse(all(rs));
    }
    return rs;
}

void solve_fuck(vector<int> b, vector<pair<int, int>> &rs) {
    int n = b.size();
    if (n == 1) {
        return;
    }
}

vector<pair<int, int>> solve_fuck(int n, int M) {
    vector<pair<int, int>> rs;
    vector<int> p(n + 1, -1);
    vector<vector<int>> t(n + 1, vector<int>());
    for (int i = 2; i <= n; i += 1) {
        for (int x = 2; x < i && x * x <= i; x += 1) {
            if (i % x == 0) {
                p[i] = p[i / x] * x;
                t[i] = t[i / x];
                break;
            }
        }
        for (int j = 1; p[i] == -1 && j < i; j += 1) {
            auto f = swp(i, j);
            if (!f.empty()) {
                p[i] = j;
                t[i] = f;
                break;
            }
        }
        if (p[i] == -1) {
            assert(0);
        }
    }
    vector<int> ra(n + 1), rb(n + 1);
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i += 1) {
        ra[i] = i;
        a[i] = i;
        rb[Get(i)] = i;
    }
    for (int k = n; k >= 2; k -= 1) {
        int psa = ra[k];
        int psb = rb[k];
        if (psa != psb) {
            int bbr = a[psb];
            vector<int> wx, wy;
            while (bbr != 1) {
                wx.push_back(bbr);
                bbr = p[bbr];
            }
            bbr = k;
            while (bbr != 1) {
                wy.push_back(bbr);
                bbr = p[bbr];
            }
            reverse(all(wy));
            auto w = wx;
            for (auto x : wy) {
                w.push_back(x);
            }
            for (auto x : w) {
                for (auto s : t[x]) {
                    if (s == 0) {
                        rs.emplace_back(ra[x], ra[p[x]]);
                    } else {
                        rs.emplace_back(ra[p[x]], ra[x]);
                    }
                }
                swap(a[ra[x]], a[ra[p[x]]]);
                swap(ra[x], ra[p[x]]);
            }
        }
    }
    return rs;
}

void SEQ(int n, int M) {
    vector<pair<int, int>> rs = solve_fuck(n, M);
    answer(1);
    for (auto [i, j] : rs) {
        add(i, j);
    }
}

/*
10 10000000 1
1 2 3 4 5 6 7 8 9 10


*/

implementer.cpp: In function ‘void {anonymous}::StAr_WaRs::main()’:
implementer.cpp:46:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   46 |                 scanf("%d %d",&n,&M);
      |                 ~~~~~^~~~~~~~~~~~~~~
implementer.cpp:47:45: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   47 |                 for (int i=1;i<=n;i++) scanf("%d",&b[i]),a[i]=i;
      |                                        ~~~~~^~~~~~~~~~~~
In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:4:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~