#include "ds.h"
#include <bits/stdc++.h>

using namespace std;
typedef int ll;
#define st first
#define nd second

struct Pair {
    ll v, mx;
};

vector<pair<ll, ll>> s;

vector<ll> rec(vector<Pair> a, ll l, ll max) {
    if (a.size() == 1) {
        if (l != max) {
            exchange(l, max);
            s.emplace_back(l, max);
        }
        return {a[0].v};
    }

    exchange(l, max);
    s.emplace_back(l, max);
    for (auto &[v, mx] : a) {
        mx = query(v + 1);
    }
    sort(a.begin(), a.end(), [](auto &v, auto &w) {
        return v.mx < w.mx;
    });

    vector<ll> ret;
    ret.push_back(a[0].v);
    vector<vector<Pair>> b = {{a[1]}};
    for (ll i = 2; i < a.size(); i++) {
        if (b.back()[0].mx == a[i].mx)
            b.back().push_back(a[i]);
        else {
            b.emplace_back();
            b.back().push_back(a[i]);
        }
    }

    l++;
    for (auto & part : b) {
        vector<ll> tmp = rec(part, l, part[0].mx);
        for (ll v: tmp)
            ret.push_back(v);
        l += (ll) part.size();
    }

    return ret;
}

void dlasciezki(ll n) {
    vector<Pair> a(n);
    for (ll v = 1; v < n; v++) {
        a[v].v = v;
        a[v].mx = query(v + 1);
    }
    sort(a.begin(), a.end(), [](auto &v, auto &w) {
        return v.mx < w.mx;
    });

    vector<ll> ret = {0};
    vector<vector<Pair>> b = {{a[1]}};
    for (ll i = 2; i < a.size(); i++) {
        if (b.back()[0].mx == a[i].mx)
            b.back().push_back(a[i]);
        else {
            b.emplace_back();
            b.back().push_back(a[i]);
        }
    }

    ll l = 1;
    for (auto & part : b) {
        vector<ll> tmp = rec(part, l, part[0].mx);
        for (ll v: tmp)
            ret.push_back(v);
        l += (ll) part.size();
    }

    vector<ll> ord(n - 1);
    std::iota(ord.begin(), ord.end(), 1);
    vector<ll> pos(n);
    std::iota(pos.begin(), pos.end(), -1);
    while (not s.empty()) {
        auto p = s.back();
        swap(pos[p.st], pos[p.nd]);
        swap(ord[pos[p.st]], ord[pos[p.nd]]);
        s.pop_back();
    }

    vector<ll> vord(n);
    for (ll i = 0; i < n; i++)
        vord[ret[i]] = i;

    vector<ll> parent(n - 1), val(n - 1);
    for (ll i = 1; i < n; i++) {
        parent[i - 1] = ret[vord[i] - 1] + 1;
        val[i - 1] = ord[vord[i] - 1];
    }

    answer(parent, val);
}

void solve(ll n, ll lim1, ll lim2) {
    if (n == 1) {
        answer(vector<ll>(), vector<ll>());
        return;
    }

    ll subtask = lim1 % 10;
    if (subtask == 1 or subtask == 3 or subtask == 6) {
        dlasciezki(n);
    }
}