sorting_network.cpp

#include "sorting_network.h"
#include "integer_set.h"

#include <algorithm>
#include <map>
#include <numeric>
#include <set>

using std::map;
using std::pair;
using std::set;
using std::vector;

void make_odd_even_merge_network(const vector<int> &a,
                                 const vector<int> &b,
                                 vector<pair<int, int>> &swaps) {
    // The generalization of Batcher's merge presented by Knuth in TAOCP Vol 3.
    if (a.empty()) {
        return;
    } else if (b.empty()) {
        return;
    } else if (a.size() == 1 && b.size() == 1) {
        swaps.emplace_back(a[0], b[0]);
        return;
    }

    vector<int> a_even, a_odd, b_even, b_odd;
    for (size_t i = 0; i < a.size(); i++) {
        if (i & 1) {
            a_odd.push_back(a[i]);
        } else {
            a_even.push_back(a[i]);
        }
    }

    for (size_t i = 0; i < b.size(); i++) {
        if (i & 1) {
            b_odd.push_back(b[i]);
        } else {
            b_even.push_back(b[i]);
        }
    }

    make_odd_even_merge_network(a_even, b_even, swaps);
    make_odd_even_merge_network(a_odd, b_odd, swaps);
    vector<int> result = a;
    result.insert(result.end(), b.begin(), b.end());
    for (size_t i = 1; i < result.size() - 1; i += 2) {
        swaps.emplace_back(result[i], result[i + 1]);
    }
}

vector<pair<int, int>> odd_even_merge(int a_start, int a_size,
                                      int b_start, int b_size,
                                      int min_idx, int max_idx) {

    // Super-optimization here hasn't revealed anything better than
    // this network for the sizes for which superoptimization works.

    // We can't possible care about elements after max_idx within
    // a, because they'd also be beyond that index in the sorted
    // list.
    int min_threshold = a_size + b_size - min_idx;
    int max_threshold = max_idx + 1;
    while (a_size > max_threshold) {
        // The last thing in a is greater than or equal to a_size
        // other values, which is greater than the threshold, so we
        // can drop it.
        a_size--;
    }
    while (b_size > max_threshold) {
        b_size--;
    }
    while (a_size > min_threshold) {
        // The first thing in a is less than or equal to a_size other
        // values, which is greater than the threshold, so we can drop
        // it.
        a_size--;
        a_start++;
        min_idx--;
        max_idx--;
    }
    while (b_size > min_threshold) {
        // The first thing in a is less than or equal to a_size other
        // values, which is greater than the threshold, so we can drop
        // it.
        b_size--;
        b_start++;
        min_idx--;
        max_idx--;
    }

    vector<pair<int, int>> swaps;
    vector<int> a_idx(a_size), b_idx(b_size);
    std::iota(a_idx.begin(), a_idx.end(), a_start);
    std::iota(b_idx.begin(), b_idx.end(), b_start);
    make_odd_even_merge_network(a_idx, b_idx, swaps);

    vector<pair<int, int>> pruned;
    set<int> needed;

    // Dump the unnecessary links as a post-pass. This is equivalent
    // to tracking which values are necessary during the recursive
    // descent, but easier to think about.
    for (int i = min_idx; i <= max_idx; i++) {
        if (i < a_size) {
            needed.insert(a_start + i);
        } else {
            needed.insert(i - a_size + b_start);
        }
    }
    for (auto it = swaps.rbegin(); it != swaps.rend(); it++) {
        if (needed.count(it->first) || needed.count(it->second)) {
            needed.insert(it->first);
            needed.insert(it->second);
            pruned.push_back(*it);
        }
    }
    std::reverse(pruned.begin(), pruned.end());

    if (min_idx == max_idx) {
        assert((int)pruned.size() < a_size + b_size && "I could do better");
    }

    return pruned;
}

vector<pair<int, int>> pairwise_sort(int size) {
    if (size <= 1) {
        return vector<pair<int, int>>{};
    } else {
        return pairwise_sort(size, 0, size - 1, false);
    }
}

// The merge step from a pairwise sorting network. Requires that the
// even elements are sorted, the odd elements are sorted, and even
// element i is <= odd element i.
vector<pair<int, int>> pairwise_merge(int size, int min_idx, int max_idx) {
    assert(min_idx <= max_idx);
    assert(min_idx >= 0);
    assert(min_idx < size);
    assert(max_idx >= 0);
    assert(max_idx < size);

    // Superoptimization yielded nothing better on these
    // networks. This may be the optimal way to merge two sorted lists
    // where there has already been a pairwise ordering across them.

    if (size <= 2) {
        return vector<pair<int, int>>{};
    }

    // Divide the elements into four groups according to their remainder mod 4.
    int size_0 = (size + 3) / 4;
    int size_1 = (size + 2) / 4;
    int size_2 = (size + 1) / 4;
    int size_3 = size / 4;

    int size_01 = size_0 + size_1;
    int size_23 = size_2 + size_3;

    assert(size_01 >= size_23);
    assert(size_01 <= size_23 + 2);

    // Figure out the final diagonal swaps we're going to do ahead of
    // time. This will help us decide how to prune the sub-merges
    // based on what we use.
    int min_idx_01 = size_01, max_idx_01 = -1;
    int min_idx_23 = size_23, max_idx_23 = -1;
    auto used = [&](int i) {
        // Map it's index into a index in the sub-merge by dropping
        // the second bit.
        int j = ((i & ~2) >> 1) | (i & 1);
        if (i & 2) {
            min_idx_23 = std::min(j, min_idx_23);
            max_idx_23 = std::max(j, min_idx_23);
        } else {
            min_idx_01 = std::min(j, min_idx_01);
            max_idx_01 = std::max(j, min_idx_01);
        }
    };
    vector<pair<int, int>> diag_swaps;
    for (int i = 1; i < size - 1; i += 2) {
        if (i <= max_idx && i + 1 >= min_idx) {
            diag_swaps.emplace_back(i, i + 1);
            used(i);
            used(i + 1);
        }
    }

    // Merge the remainder 0s with the remainder 1s. Note that the
    // remainder 0s are still pairwise sorted with the remainder 1s,
    // preserving our invariant.
    vector<pair<int, int>> even_merge;
    if (min_idx_01 <= max_idx_01) {
        even_merge = pairwise_merge(size_01, min_idx_01, max_idx_01);
    }

    // Fix the wire ids
    for (auto &p : even_merge) {
        // The even wires of the result need to land on remainder 0
        // mod 4, so they should get their index doubled. The odd
        // wires need to land on remainder 1 mod 4, so double them and
        // subtract one.
        p.first = p.first * 2 - (p.first & 1);
        p.second = p.second * 2 - (p.second & 1);
    }

    // Merge the remainder 2s with the remainder 3s. The std::max is
    // not actually necessary because of how division rounds in C, but
    // let's not rely on that or it'll be a nasty trap for anyone
    // porting this to python (you're welcome, if you're doing that).
    vector<pair<int, int>> odd_merge;
    if (min_idx_23 <= max_idx_23) {
        odd_merge = pairwise_merge(size_2 + size_3, min_idx_23, max_idx_23);
    }

    // Fix the wire ids
    for (auto &p : odd_merge) {
        // The even wires of the result need to land on remainder 2
        // mod 4, so double them and add 2. The odd
        // wires need to land on remainder 3 mod 4, so double them and
        // add one.
        p.first = p.first * 2 + 2 - (p.first & 1);
        p.second = p.second * 2 + 2 - (p.second & 1);
    }

    vector<pair<int, int>> swaps;
    swaps.swap(even_merge);
    swaps.insert(swaps.end(), odd_merge.begin(), odd_merge.end());
    swaps.insert(swaps.end(), diag_swaps.begin(), diag_swaps.end());

    return swaps;
}

vector<pair<int, int>> pairwise_sort(int size, int min_idx, int max_idx, bool sorted_pairwise, bool use_superoptimized_leaves) {
    assert(min_idx <= max_idx);
    assert(min_idx >= 0);
    assert(min_idx < size);
    assert(max_idx >= 0);
    assert(max_idx < size);

    // Normalize some equivalent cases
    if (min_idx == 1) {
        min_idx = 0;
    }
    if (max_idx == size - 2) {
        max_idx = size - 1;
    }

    // Some super-optimized special cases. (see superoptimize.cpp)
    struct Key {
        int size, min_idx, max_idx, pairwise;
        bool operator<(const Key &other) const {
            if (size < other.size) return true;
            if (size > other.size) return false;
            if (min_idx < other.min_idx) return true;
            if (min_idx > other.min_idx) return false;
            if (max_idx < other.max_idx) return true;
            if (max_idx > other.max_idx) return false;
            if (pairwise < other.pairwise) return true;
            if (pairwise > other.pairwise) return false;
            return false;
        }
    };
    static map<Key, vector<pair<int, int>>> optimal;
    static set<Key> already_optimal;
    if (optimal.empty()) {
        // Cases where the algorithm below isn't already optimal
        // (according to the superoptimizer), or where the
        // superoptimizer has certified that the algorithm below
        // produces the optimal-length network.

        already_optimal.insert({4, 0, 1, true});   // size 3
        already_optimal.insert({4, 0, 1, false});  // size 5
        already_optimal.insert({4, 0, 3, true});   // size 3
        already_optimal.insert({4, 0, 3, false});  // size 5
        already_optimal.insert({4, 2, 3, true});   // size 3
        already_optimal.insert({4, 2, 3, false});  // size 5

        already_optimal.insert({5, 0, 1, true});   // size 5
        already_optimal.insert({5, 0, 1, false});  // size 7
        already_optimal.insert({5, 0, 2, true});   // size 6
        already_optimal.insert({5, 0, 2, false});  // size 8
        optimal[{5, 2, 2, true}] = {{0, 2}, {2, 4}, {1, 3}, {1, 2}, {2, 4}};
        optimal[{5, 2, 2, false}] = {{1, 3}, {0, 4}, {3, 4}, {0, 1}, {1, 2}, {1, 3}, {2, 3}};
        already_optimal.insert({5, 0, 4, true});   // size 7
        already_optimal.insert({5, 0, 4, false});  // size 9
        optimal[{5, 2, 4, true}] = {{2, 4}, {3, 4}, {0, 3}, {1, 2}, {2, 4}, {2, 3}};
        optimal[{5, 2, 4, false}] = {{1, 3}, {0, 1}, {2, 4}, {0, 4}, {1, 3}, {1, 2}, {3, 4}, {2, 3}};
        already_optimal.insert({5, 3, 4, true});   // size 5
        already_optimal.insert({5, 3, 4, false});  // size 7

        already_optimal.insert({6, 0, 1, false});  // size 9
        already_optimal.insert({6, 0, 2, true});   // size 7
        already_optimal.insert({6, 0, 2, false});  // size 10
        already_optimal.insert({6, 0, 3, true});   // size 9
        already_optimal.insert({6, 0, 3, false});  // size 12
        optimal[{6, 2, 3, true}] = {{1, 4}, {0, 5}, {0, 2}, {3, 4}, {2, 3}, {1, 2}, {3, 5}, {2, 3}};
        optimal[{6, 2, 3, false}] = {{1, 5}, {2, 3}, {0, 1}, {0, 2}, {1, 2}, {3, 4}, {2, 4}, {3, 5}, {1, 3}, {2, 5}, {2, 3}};
        already_optimal.insert({6, 0, 5, true});   // size 9
        already_optimal.insert({6, 0, 5, false});  // size 12
        already_optimal.insert({6, 2, 5, true});   // size 9
        already_optimal.insert({6, 2, 5, false});  // size 12
        already_optimal.insert({6, 3, 5, true});   // size 7
        already_optimal.insert({6, 3, 5, false});  // size 10
        already_optimal.insert({6, 4, 5, false});  // size 9

        already_optimal.insert({7, 0, 1, false});  // size 11
        already_optimal.insert({7, 0, 2, true});   // size 9
        already_optimal.insert({7, 0, 2, false});  // size 12
        already_optimal.insert({7, 0, 3, true});   // size 12
        already_optimal.insert({7, 0, 3, false});  // size 15
        optimal[{7, 2, 3, true}] = {{1, 6}, {0, 1}, {3, 4}, {0, 3}, {1, 2}, {2, 5}, {2, 3}, {1, 2}, {3, 4}, {3, 6}, {2, 3}};
        optimal[{7, 2, 3, false}] = {{2, 3}, {0, 1}, {0, 2}, {4, 5}, {0, 4}, {1, 2}, {1, 4}, {2, 5}, {2, 3}, {2, 6}, {1, 2}, {3, 4}, {3, 6}, {2, 3}};
        optimal[{7, 3, 3, true}] = {{1, 6}, {0, 1}, {3, 4}, {0, 2}, {1, 4}, {1, 3}, {2, 3}, {3, 5}, {3, 6}, {2, 3}};
        optimal[{7, 3, 3, false}] = {{3, 5}, {0, 1}, {0, 2}, {0, 3}, {2, 6}, {1, 2}, {2, 5}, {2, 3}, {1, 2}, {2, 4}, {3, 4}, {3, 6}, {2, 3}};
        already_optimal.insert({7, 0, 4, true});   // size 12
        already_optimal.insert({7, 0, 4, false});  // size 15
        already_optimal.insert({7, 2, 4, true});   // size 12
        already_optimal.insert({7, 2, 4, false});  // size 15
        already_optimal.insert({7, 3, 4, true});   // size 11
        already_optimal.insert({7, 3, 4, false});  // size 14
        optimal[{7, 4, 4, true}] = {{1, 6}, {0, 1}, {0, 2}, {1, 4}, {2, 5}, {2, 4}, {3, 4}, {4, 5}, {4, 6}, {3, 4}};
        optimal[{7, 4, 4, false}] = {{4, 6}, {0, 1}, {0, 2}, {0, 3}, {2, 5}, {1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 6}, {3, 4}, {3, 5}, {4, 5}};
        already_optimal.insert({7, 0, 6, true});   // size 13
        already_optimal.insert({7, 0, 6, false});  // size 16
        optimal[{7, 2, 6, true}] = {{1, 6}, {0, 1}, {3, 5}, {2, 4}, {1, 2}, {3, 4}, {0, 3}, {2, 4}, {5, 6}, {3, 5}, {2, 3}, {4, 5}};
        optimal[{7, 2, 6, false}] = {{2, 3}, {0, 1}, {0, 2}, {4, 5}, {0, 4}, {1, 3}, {1, 2}, {5, 6}, {3, 6}, {4, 5}, {1, 4}, {2, 5}, {3, 4}, {2, 3}, {4, 5}};
        already_optimal.insert({7, 3, 6, true});   // size 12
        already_optimal.insert({7, 3, 6, false});  // size 15
        optimal[{7, 4, 6, true}] = {{1, 6}, {3, 5}, {0, 3}, {5, 6}, {3, 5}, {1, 3}, {2, 3}, {3, 4}, {4, 5}};
        optimal[{7, 4, 6, false}] = {{4, 6}, {0, 1}, {2, 5}, {0, 2}, {1, 3}, {2, 4}, {5, 6}, {1, 5}, {3, 6}, {3, 4}, {3, 5}, {4, 5}};
        already_optimal.insert({7, 5, 6, false});  // size 11

        // Above this point the superoptimizer is no longer
        // exhaustive, so these networks are just better than the
        // algorithm below, but not necessarily the optimal networks.

        optimal[{8, 4, 4, true}] = {{0, 2}, {2, 5}, {1, 3}, {2, 6}, {1, 6}, {4, 6}, {0, 1}, {1, 4}, {3, 5}, {3, 7}, {3, 6}, {3, 4}};
        optimal[{8, 4, 4, false}] = {{0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {2, 6}, {1, 7}, {1, 4}, {4, 6}, {0, 2}, {2, 5}, {3, 5}, {3, 7}, {3, 6}, {3, 4}};

        optimal[{9, 0, 2, true}] = {{0, 2}, {4, 6}, {0, 4}, {0, 8}, {2, 6}, {2, 8}, {2, 4}, {1, 3}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {1, 2}};
        optimal[{9, 0, 2, false}] = {{0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {2, 6}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {1, 2}};
        optimal[{9, 2, 2, true}] = {{0, 2}, {4, 6}, {0, 4}, {2, 6}, {2, 8}, {2, 4}, {1, 3}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {1, 2}};
        optimal[{9, 2, 2, false}] = {{0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {2, 6}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {1, 2}};
        optimal[{9, 0, 3, true}] = {{0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {1, 3}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 6}, {3, 4}};
        optimal[{9, 0, 3, false}] = {{0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 6}, {3, 4}};
        optimal[{9, 2, 3, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {1, 3}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 6}, {3, 4}};
        optimal[{9, 2, 3, false}] = {{0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 6}, {3, 4}};
        optimal[{9, 3, 3, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {1, 3}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 6}, {3, 4}};
        optimal[{9, 3, 3, false}] = {{0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 6}, {3, 4}};
        optimal[{9, 2, 4, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 6}, {3, 4}};
        optimal[{9, 2, 4, false}] = {{0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 6}, {3, 4}};
        optimal[{9, 3, 4, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 6}, {3, 4}};
        optimal[{9, 3, 4, false}] = {{0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 6}, {3, 4}};
        optimal[{9, 4, 4, true}] = {{2, 6}, {0, 2}, {4, 6}, {2, 4}, {4, 8}, {4, 6}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 6}, {3, 4}};
        optimal[{9, 4, 4, false}] = {{0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {1, 5}, {1, 7}, {1, 2}, {2, 8}, {5, 8}, {2, 4}, {3, 5}, {3, 7}, {3, 6}, {3, 4}};
        optimal[{9, 2, 5, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {1, 2}, {3, 7}, {3, 5}, {5, 8}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{9, 2, 5, false}] = {{0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {1, 2}, {3, 7}, {3, 5}, {5, 8}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{9, 3, 5, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {3, 7}, {3, 5}, {5, 8}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{9, 3, 5, false}] = {{0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {3, 7}, {3, 5}, {5, 8}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{9, 4, 5, true}] = {{2, 6}, {0, 2}, {4, 6}, {2, 4}, {4, 8}, {4, 6}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {3, 7}, {3, 5}, {5, 8}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{9, 4, 5, false}] = {{0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {6, 7}, {3, 8}, {1, 5}, {5, 7}, {3, 5}, {1, 6}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{9, 2, 6, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {1, 2}, {3, 7}, {3, 5}, {5, 8}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{9, 2, 6, false}] = {{0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {1, 2}, {3, 7}, {3, 5}, {5, 8}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{9, 3, 6, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {3, 7}, {3, 5}, {5, 8}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{9, 3, 6, false}] = {{0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {3, 7}, {3, 5}, {5, 8}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{9, 4, 6, true}] = {{0, 2}, {4, 6}, {2, 6}, {0, 2}, {6, 8}, {2, 4}, {1, 3}, {4, 6}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {3, 7}, {3, 5}, {5, 8}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{9, 4, 6, false}] = {{0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {1, 5}, {1, 8}, {1, 4}, {3, 7}, {3, 5}, {5, 8}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{9, 6, 6, true}] = {{4, 6}, {0, 2}, {2, 8}, {6, 8}, {2, 6}, {1, 3}, {5, 7}, {1, 5}, {3, 7}, {3, 5}, {5, 8}, {3, 6}, {5, 6}};
        optimal[{9, 6, 6, false}] = {{0, 1}, {2, 3}, {0, 2}, {2, 8}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {6, 8}, {2, 6}, {5, 7}, {1, 5}, {3, 7}, {3, 5}, {5, 8}, {3, 6}, {5, 6}};
        optimal[{9, 2, 8, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {3, 7}, {1, 5}, {3, 5}, {3, 6}, {1, 8}, {1, 4}, {1, 2}, {3, 4}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{9, 2, 8, false}] = {{0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {3, 7}, {1, 5}, {3, 5}, {3, 6}, {1, 8}, {1, 4}, {1, 2}, {3, 4}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{9, 3, 8, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {3, 7}, {1, 5}, {3, 5}, {3, 6}, {1, 8}, {1, 4}, {3, 4}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{9, 3, 8, false}] = {{0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {3, 7}, {1, 5}, {3, 5}, {3, 6}, {1, 8}, {1, 4}, {3, 4}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{9, 4, 8, true}] = {{0, 2}, {4, 6}, {2, 6}, {0, 2}, {6, 8}, {2, 4}, {1, 3}, {4, 6}, {5, 7}, {3, 7}, {1, 5}, {3, 5}, {3, 6}, {1, 8}, {1, 4}, {3, 4}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{9, 4, 8, false}] = {{0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {3, 7}, {1, 5}, {3, 5}, {3, 6}, {1, 8}, {1, 4}, {3, 4}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{9, 6, 8, true}] = {{4, 6}, {0, 2}, {2, 8}, {6, 8}, {2, 6}, {1, 3}, {5, 7}, {1, 5}, {3, 7}, {3, 5}, {3, 6}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{9, 6, 8, false}] = {{0, 1}, {2, 3}, {0, 2}, {2, 8}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {6, 8}, {2, 6}, {5, 7}, {1, 5}, {3, 7}, {3, 5}, {3, 6}, {5, 8}, {5, 6}, {7, 8}};

        optimal[{10, 0, 2, true}] = {{0, 2}, {4, 6}, {0, 4}, {0, 8}, {2, 6}, {2, 8}, {2, 4}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}};
        optimal[{10, 0, 2, false}] = {{8, 9}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {2, 6}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}};
        optimal[{10, 2, 2, true}] = {{0, 2}, {4, 6}, {0, 4}, {0, 8}, {2, 6}, {2, 8}, {2, 4}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}};
        optimal[{10, 2, 2, false}] = {{8, 9}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {2, 6}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}};
        optimal[{10, 0, 3, true}] = {{0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 6}, {3, 4}};
        optimal[{10, 0, 3, false}] = {{8, 9}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 6}, {3, 4}};
        optimal[{10, 2, 3, true}] = {{0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 6}, {3, 4}};
        optimal[{10, 2, 3, false}] = {{8, 9}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 6}, {3, 4}};
        optimal[{10, 3, 3, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 6}, {3, 4}};
        optimal[{10, 3, 3, false}] = {{8, 9}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 6}, {3, 4}};
        optimal[{10, 3, 4, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 6}, {3, 4}};
        optimal[{10, 3, 4, false}] = {{8, 9}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 6}, {3, 4}};
        optimal[{10, 4, 4, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 6}, {3, 4}};
        optimal[{10, 4, 4, false}] = {{8, 9}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {1, 7}, {5, 8}, {1, 5}, {3, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 6}, {3, 4}};
        optimal[{10, 3, 5, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {5, 9}, {3, 7}, {3, 9}, {3, 5}, {5, 8}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{10, 3, 5, false}] = {{8, 9}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {5, 9}, {3, 7}, {3, 9}, {3, 5}, {5, 8}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{10, 4, 5, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 9}, {1, 6}, {5, 8}, {3, 5}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{10, 4, 5, false}] = {{8, 9}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 9}, {1, 6}, {5, 8}, {3, 5}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{10, 3, 6, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {5, 9}, {3, 7}, {3, 9}, {3, 5}, {5, 8}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{10, 3, 6, false}] = {{8, 9}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {5, 9}, {3, 7}, {3, 9}, {3, 5}, {5, 8}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{10, 4, 6, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {5, 9}, {3, 7}, {3, 9}, {3, 5}, {5, 8}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{10, 4, 6, false}] = {{8, 9}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {5, 9}, {3, 7}, {3, 9}, {3, 5}, {5, 8}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{10, 6, 6, true}] = {{4, 6}, {0, 2}, {2, 8}, {6, 8}, {0, 6}, {2, 6}, {4, 6}, {1, 3}, {5, 7}, {1, 5}, {1, 8}, {5, 9}, {3, 7}, {3, 9}, {3, 5}, {5, 8}, {3, 6}, {5, 6}};
        optimal[{10, 6, 6, false}] = {{8, 9}, {0, 1}, {2, 3}, {0, 2}, {2, 8}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {6, 8}, {0, 6}, {2, 6}, {4, 6}, {5, 7}, {1, 5}, {1, 8}, {5, 9}, {3, 7}, {3, 9}, {3, 5}, {5, 8}, {3, 6}, {5, 6}};
        optimal[{10, 3, 7, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {3, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 9}, {7, 9}, {3, 5}, {3, 6}, {1, 8}, {1, 4}, {3, 4}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{10, 3, 7, false}] = {{8, 9}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {3, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 9}, {7, 9}, {3, 5}, {3, 6}, {1, 8}, {1, 4}, {3, 4}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{10, 4, 7, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {3, 7}, {1, 5}, {3, 9}, {1, 6}, {5, 8}, {3, 5}, {3, 6}, {8, 9}, {1, 4}, {3, 4}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{10, 4, 7, false}] = {{8, 9}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {3, 7}, {1, 5}, {3, 9}, {1, 6}, {5, 8}, {3, 5}, {3, 6}, {8, 9}, {1, 4}, {3, 4}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{10, 5, 7, true}] = {{4, 6}, {0, 2}, {2, 8}, {6, 8}, {0, 6}, {2, 6}, {4, 6}, {1, 3}, {5, 7}, {3, 7}, {1, 5}, {3, 5}, {8, 9}, {3, 8}, {1, 6}, {3, 6}, {5, 9}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{10, 5, 7, false}] = {{8, 9}, {0, 1}, {2, 3}, {0, 2}, {2, 8}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {6, 8}, {0, 6}, {2, 6}, {4, 6}, {5, 7}, {3, 7}, {1, 5}, {3, 5}, {8, 9}, {3, 8}, {1, 6}, {3, 6}, {5, 9}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{10, 6, 7, true}] = {{4, 6}, {0, 2}, {2, 8}, {6, 8}, {0, 6}, {2, 6}, {4, 6}, {1, 3}, {5, 7}, {3, 7}, {1, 5}, {5, 9}, {3, 9}, {7, 9}, {3, 5}, {3, 6}, {1, 8}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{10, 6, 7, false}] = {{8, 9}, {0, 1}, {2, 3}, {0, 2}, {2, 8}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {6, 8}, {0, 6}, {2, 6}, {4, 6}, {5, 7}, {3, 7}, {1, 5}, {5, 9}, {3, 9}, {7, 9}, {3, 5}, {3, 6}, {1, 8}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{10, 7, 7, true}] = {{5, 7}, {4, 6}, {0, 2}, {2, 8}, {6, 8}, {3, 9}, {1, 3}, {3, 9}, {3, 5}, {7, 9}, {5, 7}, {1, 8}, {5, 8}, {7, 8}};
        optimal[{10, 7, 7, false}] = {{4, 5}, {6, 7}, {5, 7}, {4, 6}, {8, 9}, {0, 1}, {2, 3}, {0, 2}, {2, 8}, {6, 8}, {3, 9}, {1, 3}, {3, 9}, {3, 5}, {7, 9}, {5, 7}, {1, 8}, {5, 8}, {7, 8}};
        optimal[{10, 3, 9, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {3, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 9}, {7, 9}, {3, 5}, {3, 6}, {1, 8}, {1, 4}, {3, 4}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{10, 3, 9, false}] = {{8, 9}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {3, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 9}, {7, 9}, {3, 5}, {3, 6}, {1, 8}, {1, 4}, {3, 4}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{10, 4, 9, true}] = {{0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {3, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 9}, {7, 9}, {3, 5}, {3, 6}, {1, 8}, {1, 4}, {3, 4}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{10, 4, 9, false}] = {{8, 9}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {3, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 9}, {7, 9}, {3, 5}, {3, 6}, {1, 8}, {1, 4}, {3, 4}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{10, 6, 9, true}] = {{4, 6}, {0, 2}, {2, 8}, {6, 8}, {0, 6}, {2, 6}, {4, 6}, {1, 3}, {5, 7}, {3, 7}, {1, 5}, {5, 9}, {3, 9}, {7, 9}, {3, 5}, {3, 6}, {1, 8}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{10, 6, 9, false}] = {{8, 9}, {0, 1}, {2, 3}, {0, 2}, {2, 8}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {6, 8}, {0, 6}, {2, 6}, {4, 6}, {5, 7}, {3, 7}, {1, 5}, {5, 9}, {3, 9}, {7, 9}, {3, 5}, {3, 6}, {1, 8}, {5, 8}, {5, 6}, {7, 8}};
        optimal[{10, 7, 9, true}] = {{5, 7}, {4, 6}, {0, 2}, {2, 8}, {6, 8}, {8, 9}, {7, 9}, {1, 3}, {3, 7}, {3, 5}, {7, 9}, {1, 8}, {5, 8}, {7, 8}};
        optimal[{10, 7, 9, false}] = {{4, 5}, {6, 7}, {5, 7}, {4, 6}, {8, 9}, {0, 1}, {2, 3}, {0, 2}, {2, 8}, {6, 8}, {8, 9}, {7, 9}, {1, 3}, {3, 7}, {3, 5}, {7, 9}, {1, 8}, {5, 8}, {7, 8}};

        optimal[{11, 0, 2, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}};
        optimal[{11, 0, 2, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}};
        optimal[{11, 2, 2, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}};
        optimal[{11, 2, 2, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}};
        optimal[{11, 0, 3, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 10}, {3, 6}, {3, 4}};
        optimal[{11, 0, 3, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 10}, {3, 6}, {3, 4}};
        optimal[{11, 2, 3, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 10}, {3, 6}, {3, 4}};
        optimal[{11, 2, 3, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 10}, {3, 6}, {3, 4}};
        optimal[{11, 3, 3, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 10}, {3, 6}, {3, 4}};
        optimal[{11, 3, 3, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 10}, {3, 6}, {3, 4}};
        optimal[{11, 0, 4, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 6}, {3, 4}};
        optimal[{11, 0, 4, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 6}, {3, 4}};
        optimal[{11, 2, 4, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 6}, {3, 4}};
        optimal[{11, 2, 4, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 6}, {3, 4}};
        optimal[{11, 3, 4, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 6}, {3, 4}};
        optimal[{11, 3, 4, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 6}, {3, 4}};
        optimal[{11, 4, 4, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {2, 8}, {2, 4}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 6}, {3, 4}};
        optimal[{11, 4, 4, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 6}, {3, 4}};
        optimal[{11, 4, 5, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {5, 9}, {3, 7}, {3, 9}, {3, 5}, {5, 8}, {3, 10}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{11, 4, 5, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 7}, {1, 5}, {1, 6}, {8, 9}, {1, 8}, {6, 8}, {3, 7}, {3, 9}, {3, 5}, {5, 8}, {3, 10}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{11, 4, 6, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {5, 9}, {3, 7}, {3, 9}, {3, 5}, {5, 8}, {3, 10}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{11, 4, 6, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {5, 9}, {3, 7}, {3, 9}, {3, 5}, {5, 8}, {3, 10}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{11, 6, 6, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {6, 10}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 9}, {3, 5}, {5, 8}, {3, 10}, {3, 6}, {5, 6}};
        optimal[{11, 6, 6, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {6, 10}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 9}, {3, 5}, {5, 8}, {3, 10}, {3, 6}, {5, 6}};
        optimal[{11, 4, 7, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {5, 9}, {3, 7}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {3, 6}, {3, 4}, {5, 6}, {7, 10}, {7, 8}};
        optimal[{11, 4, 7, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {5, 9}, {3, 7}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {3, 6}, {3, 4}, {5, 6}, {7, 10}, {7, 8}};
        optimal[{11, 6, 7, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {6, 10}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {3, 6}, {5, 6}, {7, 10}, {7, 8}};
        optimal[{11, 6, 7, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {6, 10}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {3, 6}, {5, 6}, {7, 10}, {7, 8}};
        optimal[{11, 7, 7, true}] = {{4, 6}, {0, 2}, {8, 10}, {0, 8}, {2, 10}, {2, 8}, {4, 8}, {6, 10}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {7, 10}, {7, 8}};
        optimal[{11, 7, 7, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {0, 8}, {2, 10}, {2, 8}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {4, 8}, {6, 10}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {7, 10}, {7, 8}};
        optimal[{11, 4, 8, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {5, 9}, {3, 7}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {3, 6}, {3, 4}, {5, 6}, {7, 10}, {7, 8}};
        optimal[{11, 4, 8, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {5, 9}, {3, 7}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {3, 6}, {3, 4}, {5, 6}, {7, 10}, {7, 8}};
        optimal[{11, 6, 8, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {6, 10}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {3, 6}, {5, 6}, {7, 10}, {7, 8}};
        optimal[{11, 6, 8, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {6, 10}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {3, 6}, {5, 6}, {7, 10}, {7, 8}};
        optimal[{11, 7, 8, true}] = {{4, 6}, {0, 2}, {8, 10}, {0, 8}, {2, 10}, {2, 8}, {4, 8}, {6, 10}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {7, 10}, {7, 8}};
        optimal[{11, 7, 8, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {0, 8}, {2, 10}, {2, 8}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {4, 8}, {6, 10}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {7, 10}, {7, 8}};
        optimal[{11, 8, 8, true}] = {{4, 6}, {0, 2}, {8, 10}, {2, 10}, {2, 8}, {6, 10}, {6, 8}, {1, 3}, {1, 9}, {1, 8}, {5, 7}, {5, 9}, {5, 8}, {3, 7}, {3, 9}, {7, 9}, {3, 10}, {7, 10}, {7, 8}};
        optimal[{11, 8, 8, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {2, 10}, {2, 8}, {1, 3}, {1, 9}, {4, 5}, {6, 7}, {4, 6}, {6, 10}, {6, 8}, {1, 8}, {5, 7}, {5, 9}, {5, 8}, {3, 7}, {3, 9}, {7, 9}, {3, 10}, {7, 10}, {7, 8}};
        optimal[{11, 4, 10, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {5, 9}, {3, 7}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {3, 6}, {3, 4}, {5, 6}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{11, 4, 10, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {5, 9}, {3, 7}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {3, 6}, {3, 4}, {5, 6}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{11, 6, 10, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {6, 10}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {3, 6}, {5, 6}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{11, 6, 10, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 8}, {6, 10}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {3, 6}, {5, 6}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{11, 7, 10, true}] = {{4, 6}, {0, 2}, {8, 10}, {0, 8}, {2, 10}, {2, 8}, {4, 8}, {6, 10}, {6, 8}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{11, 7, 10, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {0, 8}, {2, 10}, {2, 8}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {4, 8}, {6, 10}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{11, 8, 10, true}] = {{4, 6}, {0, 2}, {8, 10}, {2, 10}, {2, 8}, {6, 10}, {6, 8}, {1, 3}, {1, 9}, {1, 8}, {5, 7}, {5, 9}, {5, 8}, {3, 7}, {3, 9}, {7, 9}, {3, 10}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{11, 8, 10, false}] = {{8, 9}, {8, 10}, {0, 1}, {2, 3}, {0, 2}, {2, 10}, {2, 8}, {1, 3}, {1, 9}, {4, 5}, {6, 7}, {4, 6}, {6, 10}, {6, 8}, {1, 8}, {5, 7}, {5, 9}, {5, 8}, {3, 7}, {3, 9}, {7, 9}, {3, 10}, {7, 10}, {7, 8}, {9, 10}};

        optimal[{12, 0, 2, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}};
        optimal[{12, 0, 2, false}] = {{8, 9}, {10, 11}, {8, 10}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}};
        optimal[{12, 2, 2, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}};
        optimal[{12, 2, 2, false}] = {{8, 9}, {10, 11}, {8, 10}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}};
        optimal[{12, 0, 3, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 10}, {3, 6}, {3, 4}};
        optimal[{12, 0, 3, false}] = {{8, 9}, {10, 11}, {8, 10}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 10}, {3, 6}, {3, 4}};
        optimal[{12, 2, 3, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 10}, {3, 6}, {3, 4}};
        optimal[{12, 2, 3, false}] = {{8, 9}, {10, 11}, {8, 10}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 10}, {3, 6}, {3, 4}};
        optimal[{12, 3, 3, false}] = {{8, 9}, {10, 11}, {8, 10}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 10}, {3, 6}, {3, 4}};
        optimal[{12, 0, 4, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {2, 8}, {2, 4}, {6, 8}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 6}, {3, 4}};
        optimal[{12, 0, 4, false}] = {{8, 9}, {10, 11}, {8, 10}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 6}, {3, 4}};
        optimal[{12, 2, 4, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {2, 8}, {2, 4}, {6, 8}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 6}, {3, 4}};
        optimal[{12, 2, 4, false}] = {{8, 9}, {10, 11}, {8, 10}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 6}, {3, 4}};
        optimal[{12, 3, 4, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {2, 8}, {2, 4}, {6, 8}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 6}, {3, 4}};
        optimal[{12, 3, 4, false}] = {{8, 9}, {10, 11}, {8, 10}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 6}, {3, 4}};
        optimal[{12, 4, 4, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {2, 8}, {2, 4}, {6, 8}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 6}, {3, 4}};
        optimal[{12, 4, 4, false}] = {{8, 9}, {10, 11}, {8, 10}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {2, 8}, {2, 4}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 6}, {3, 4}};
        optimal[{12, 6, 7, true}] = {{8, 10}, {0, 2}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 8}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {5, 10}, {3, 8}, {7, 11}, {3, 5}, {8, 9}, {5, 8}, {5, 6}, {7, 10}, {7, 8}};
        optimal[{12, 6, 7, false}] = {{8, 9}, {10, 11}, {8, 10}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {5, 10}, {3, 8}, {7, 11}, {3, 5}, {8, 9}, {5, 8}, {5, 6}, {7, 10}, {7, 8}};
        optimal[{12, 7, 7, true}] = {{4, 6}, {0, 2}, {8, 10}, {0, 8}, {2, 10}, {2, 8}, {4, 8}, {6, 10}, {6, 8}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {7, 10}, {7, 8}};
        optimal[{12, 7, 7, false}] = {{8, 9}, {10, 11}, {8, 10}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {0, 8}, {2, 10}, {2, 8}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {4, 8}, {6, 10}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {7, 10}, {7, 8}};
        optimal[{12, 7, 8, true}] = {{4, 6}, {0, 2}, {8, 10}, {0, 8}, {2, 10}, {2, 8}, {4, 8}, {6, 10}, {6, 8}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {7, 10}, {7, 8}};
        optimal[{12, 7, 8, false}] = {{8, 9}, {10, 11}, {8, 10}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {0, 8}, {2, 10}, {2, 8}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {4, 8}, {6, 10}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {7, 10}, {7, 8}};
        optimal[{12, 8, 8, true}] = {{4, 6}, {0, 2}, {8, 10}, {0, 8}, {2, 10}, {2, 8}, {4, 8}, {6, 10}, {6, 8}, {9, 11}, {1, 3}, {1, 9}, {1, 8}, {5, 7}, {5, 9}, {5, 8}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 10}, {7, 10}, {7, 8}};
        optimal[{12, 8, 8, false}] = {{8, 9}, {10, 11}, {8, 10}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {0, 8}, {2, 10}, {2, 8}, {1, 3}, {1, 9}, {4, 5}, {6, 7}, {4, 6}, {4, 8}, {6, 10}, {6, 8}, {1, 8}, {5, 7}, {5, 9}, {5, 8}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 10}, {7, 10}, {7, 8}};
        optimal[{12, 7, 9, true}] = {{4, 6}, {0, 2}, {8, 10}, {0, 8}, {2, 10}, {2, 8}, {4, 8}, {6, 10}, {6, 8}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{12, 7, 9, false}] = {{8, 9}, {10, 11}, {8, 10}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {0, 8}, {2, 10}, {2, 8}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {4, 8}, {6, 10}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{12, 8, 9, true}] = {{4, 6}, {0, 2}, {8, 10}, {0, 8}, {2, 10}, {2, 8}, {4, 8}, {6, 10}, {6, 8}, {9, 11}, {1, 3}, {1, 9}, {1, 8}, {5, 7}, {5, 9}, {5, 8}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 10}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{12, 8, 9, false}] = {{8, 9}, {10, 11}, {8, 10}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {0, 8}, {2, 10}, {2, 8}, {1, 3}, {1, 9}, {4, 5}, {6, 7}, {4, 6}, {4, 8}, {6, 10}, {6, 8}, {1, 8}, {5, 7}, {5, 9}, {5, 8}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 10}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{12, 9, 9, true}] = {{4, 6}, {0, 2}, {8, 10}, {2, 10}, {6, 10}, {5, 7}, {1, 3}, {1, 5}, {9, 11}, {5, 9}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 10}, {7, 10}, {9, 10}};
        optimal[{12, 9, 9, false}] = {{4, 5}, {6, 7}, {4, 6}, {5, 7}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {1, 5}, {8, 9}, {10, 11}, {8, 10}, {2, 10}, {6, 10}, {9, 11}, {5, 9}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 10}, {7, 10}, {9, 10}};
        optimal[{12, 7, 11, true}] = {{4, 6}, {0, 2}, {8, 10}, {0, 8}, {2, 10}, {2, 8}, {4, 8}, {6, 10}, {6, 8}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{12, 7, 11, false}] = {{8, 9}, {10, 11}, {8, 10}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {0, 8}, {2, 10}, {2, 8}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {4, 8}, {6, 10}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 8}, {3, 10}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{12, 8, 11, true}] = {{4, 6}, {0, 2}, {8, 10}, {0, 8}, {2, 10}, {2, 8}, {4, 8}, {6, 10}, {6, 8}, {9, 11}, {1, 3}, {1, 9}, {1, 8}, {5, 7}, {5, 9}, {5, 8}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 10}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{12, 8, 11, false}] = {{8, 9}, {10, 11}, {8, 10}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {0, 8}, {2, 10}, {2, 8}, {1, 3}, {1, 9}, {4, 5}, {6, 7}, {4, 6}, {4, 8}, {6, 10}, {6, 8}, {1, 8}, {5, 7}, {5, 9}, {5, 8}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 10}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{12, 9, 11, true}] = {{4, 6}, {0, 2}, {8, 10}, {2, 10}, {6, 10}, {5, 7}, {1, 3}, {1, 5}, {9, 11}, {5, 9}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 10}, {7, 10}, {9, 10}};
        optimal[{12, 9, 11, false}] = {{4, 5}, {6, 7}, {4, 6}, {5, 7}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {1, 5}, {8, 9}, {10, 11}, {8, 10}, {2, 10}, {6, 10}, {9, 11}, {5, 9}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 10}, {7, 10}, {9, 10}};

        optimal[{13, 0, 2, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 12}, {0, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}};
        optimal[{13, 2, 2, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 12}, {0, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}};
        optimal[{13, 0, 3, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {6, 12}, {2, 10}, {2, 8}, {2, 4}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 10}, {3, 6}, {3, 4}};
        optimal[{13, 0, 3, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {6, 12}, {2, 10}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 10}, {3, 6}, {3, 4}};
        optimal[{13, 2, 3, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {6, 12}, {2, 10}, {2, 8}, {2, 4}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 10}, {3, 6}, {3, 4}};
        optimal[{13, 2, 3, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {6, 12}, {2, 10}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 10}, {3, 6}, {3, 4}};
        optimal[{13, 3, 3, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {6, 12}, {2, 10}, {2, 8}, {2, 4}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 10}, {3, 6}, {3, 4}};
        optimal[{13, 3, 3, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {6, 12}, {2, 10}, {2, 8}, {2, 4}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 10}, {3, 6}, {3, 4}};
        optimal[{13, 0, 4, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 12}, {6, 8}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 6}, {3, 4}};
        optimal[{13, 0, 4, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 12}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 6}, {3, 4}};
        optimal[{13, 2, 4, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 12}, {6, 8}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 6}, {3, 4}};
        optimal[{13, 2, 4, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 12}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 6}, {3, 4}};
        optimal[{13, 3, 4, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 12}, {6, 8}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 6}, {3, 4}};
        optimal[{13, 3, 4, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 12}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 6}, {3, 4}};
        optimal[{13, 4, 4, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 12}, {6, 8}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 6}, {3, 4}};
        optimal[{13, 4, 4, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 12}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {3, 5}, {3, 7}, {3, 9}, {3, 11}, {3, 6}, {3, 4}};
        optimal[{13, 0, 5, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 12}, {6, 8}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {5, 9}, {3, 7}, {3, 11}, {3, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{13, 0, 5, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 12}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {5, 9}, {3, 7}, {3, 11}, {3, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{13, 2, 5, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 12}, {6, 8}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {5, 9}, {3, 7}, {3, 11}, {3, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{13, 2, 5, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 12}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {1, 2}, {5, 9}, {3, 7}, {3, 11}, {3, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{13, 3, 5, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 12}, {6, 8}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {5, 9}, {3, 7}, {3, 11}, {3, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{13, 3, 5, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 12}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {5, 9}, {3, 7}, {3, 11}, {3, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{13, 4, 5, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 12}, {6, 8}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {5, 9}, {3, 7}, {3, 11}, {3, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{13, 4, 5, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {2, 4}, {6, 10}, {6, 12}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {1, 4}, {5, 9}, {3, 7}, {3, 11}, {3, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {3, 6}, {3, 4}, {5, 6}};
        optimal[{13, 5, 5, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {3, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {3, 6}, {5, 6}};
        optimal[{13, 5, 5, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {0, 8}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {3, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {3, 6}, {5, 6}};
        optimal[{13, 6, 6, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {3, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {3, 6}, {5, 6}};
        optimal[{13, 6, 6, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {3, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {3, 6}, {5, 6}};
        optimal[{13, 6, 7, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {3, 6}, {5, 6}, {7, 10}, {7, 8}};
        optimal[{13, 6, 7, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {3, 6}, {5, 6}, {7, 10}, {7, 8}};
        optimal[{13, 7, 7, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {7, 10}, {7, 8}};
        optimal[{13, 7, 7, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {7, 10}, {7, 8}};
        optimal[{13, 6, 8, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {3, 6}, {5, 6}, {7, 10}, {7, 8}};
        optimal[{13, 6, 8, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {3, 6}, {5, 6}, {7, 10}, {7, 8}};
        optimal[{13, 7, 8, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {7, 10}, {7, 8}};
        optimal[{13, 7, 8, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {7, 10}, {7, 8}};
        optimal[{13, 8, 8, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {7, 10}, {7, 8}};
        optimal[{13, 8, 8, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 12}, {5, 8}, {3, 10}, {7, 10}, {7, 8}};
        optimal[{13, 6, 9, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 12}, {5, 8}, {9, 12}, {3, 10}, {3, 6}, {5, 6}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{13, 6, 9, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 12}, {5, 8}, {9, 12}, {3, 10}, {3, 6}, {5, 6}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{13, 7, 9, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 12}, {5, 8}, {9, 12}, {3, 10}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{13, 7, 9, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 12}, {5, 8}, {9, 12}, {3, 10}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{13, 8, 9, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {5, 12}, {3, 10}, {9, 12}, {5, 8}, {7, 9}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{13, 8, 9, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {5, 12}, {3, 10}, {9, 12}, {5, 8}, {7, 9}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{13, 9, 9, true}] = {{8, 10}, {4, 6}, {0, 2}, {2, 12}, {6, 12}, {10, 12}, {0, 10}, {2, 10}, {4, 10}, {6, 10}, {8, 10}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {5, 12}, {7, 11}, {7, 12}, {7, 9}, {3, 7}, {7, 10}, {9, 10}};
        optimal[{13, 9, 9, false}] = {{8, 9}, {10, 11}, {8, 10}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {2, 12}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {6, 12}, {10, 12}, {0, 10}, {2, 10}, {4, 10}, {6, 10}, {8, 10}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {5, 12}, {7, 11}, {7, 12}, {7, 9}, {3, 7}, {7, 10}, {9, 10}};
        optimal[{13, 6, 10, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 12}, {5, 8}, {9, 12}, {3, 10}, {3, 6}, {5, 6}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{13, 6, 10, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 12}, {5, 8}, {9, 12}, {3, 10}, {3, 6}, {5, 6}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{13, 7, 10, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 12}, {5, 8}, {9, 12}, {3, 10}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{13, 7, 10, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 12}, {5, 8}, {9, 12}, {3, 10}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{13, 8, 10, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 12}, {5, 8}, {9, 12}, {3, 10}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{13, 8, 10, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {5, 12}, {5, 8}, {9, 12}, {3, 10}, {7, 10}, {7, 8}, {9, 10}};
        optimal[{13, 9, 10, true}] = {{8, 10}, {4, 6}, {0, 2}, {2, 12}, {6, 12}, {10, 12}, {0, 10}, {2, 10}, {4, 10}, {6, 10}, {8, 10}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {3, 5}, {5, 12}, {7, 9}, {9, 12}, {7, 10}, {9, 10}};
        optimal[{13, 9, 10, false}] = {{8, 9}, {10, 11}, {8, 10}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {2, 12}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {6, 12}, {10, 12}, {0, 10}, {2, 10}, {4, 10}, {6, 10}, {8, 10}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {3, 5}, {5, 12}, {7, 9}, {9, 12}, {7, 10}, {9, 10}};
        optimal[{13, 10, 10, true}] = {{8, 10}, {4, 6}, {0, 2}, {2, 12}, {6, 12}, {10, 12}, {2, 10}, {6, 10}, {5, 7}, {1, 3}, {1, 5}, {9, 11}, {5, 9}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {9, 12}, {3, 10}, {7, 10}, {9, 10}};
        optimal[{13, 10, 10, false}] = {{4, 5}, {6, 7}, {4, 6}, {5, 7}, {0, 1}, {2, 3}, {0, 2}, {2, 12}, {6, 12}, {1, 3}, {1, 5}, {8, 9}, {10, 11}, {8, 10}, {10, 12}, {2, 10}, {6, 10}, {9, 11}, {5, 9}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {9, 12}, {3, 10}, {7, 10}, {9, 10}};
        optimal[{13, 6, 12, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {3, 10}, {3, 6}, {7, 10}, {5, 12}, {5, 8}, {5, 6}, {7, 8}, {9, 12}, {9, 10}, {11, 12}};
        optimal[{13, 6, 12, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {3, 10}, {3, 6}, {7, 10}, {5, 12}, {5, 8}, {5, 6}, {7, 8}, {9, 12}, {9, 10}, {11, 12}};
        optimal[{13, 7, 12, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {3, 10}, {7, 10}, {5, 12}, {5, 8}, {7, 8}, {9, 12}, {9, 10}, {11, 12}};
        optimal[{13, 7, 12, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {2, 8}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {5, 7}, {1, 5}, {1, 9}, {1, 8}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {3, 10}, {7, 10}, {5, 12}, {5, 8}, {7, 8}, {9, 12}, {9, 10}, {11, 12}};
        optimal[{13, 8, 12, true}] = {{8, 10}, {8, 12}, {0, 2}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {3, 10}, {7, 10}, {5, 12}, {5, 8}, {7, 8}, {9, 12}, {9, 10}, {11, 12}};
        optimal[{13, 8, 12, false}] = {{8, 9}, {10, 11}, {8, 10}, {8, 12}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {0, 4}, {4, 12}, {4, 8}, {2, 6}, {2, 10}, {6, 10}, {6, 12}, {6, 8}, {10, 12}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {3, 5}, {3, 10}, {7, 10}, {5, 12}, {5, 8}, {7, 8}, {9, 12}, {9, 10}, {11, 12}};
        optimal[{13, 9, 12, true}] = {{8, 10}, {4, 6}, {0, 2}, {2, 12}, {6, 12}, {10, 12}, {0, 10}, {2, 10}, {4, 10}, {6, 10}, {8, 10}, {9, 11}, {1, 3}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {7, 10}, {3, 5}, {5, 12}, {9, 12}, {9, 10}, {11, 12}};
        optimal[{13, 9, 12, false}] = {{8, 9}, {10, 11}, {8, 10}, {9, 11}, {0, 1}, {2, 3}, {0, 2}, {2, 12}, {1, 3}, {4, 5}, {6, 7}, {4, 6}, {6, 12}, {10, 12}, {0, 10}, {2, 10}, {4, 10}, {6, 10}, {8, 10}, {5, 7}, {1, 5}, {1, 9}, {5, 9}, {3, 7}, {3, 11}, {7, 11}, {3, 9}, {7, 9}, {7, 10}, {3, 5}, {5, 12}, {9, 12}, {9, 10}, {11, 12}};
        optimal[{13, 10, 12, true}] = {{8, 10}, {4, 6}, {0, 2}, {2, 12}, {6, 12}, {10, 12}, {2, 10}, {6, 10}, {5, 7}, {1, 3}, {1, 5}, {9, 11}, {5, 9}, {3, 11}, {7, 11}, {3, 9}, {3, 10}, {7, 9}, {7, 10}, {9, 12}, {9, 10}, {11, 12}};
        optimal[{13, 10, 12, false}] = {{4, 5}, {6, 7}, {4, 6}, {5, 7}, {0, 1}, {2, 3}, {0, 2}, {2, 12}, {6, 12}, {1, 3}, {1, 5}, {8, 9}, {10, 11}, {8, 10}, {10, 12}, {2, 10}, {6, 10}, {9, 11}, {5, 9}, {3, 11}, {7, 11}, {3, 9}, {3, 10}, {7, 9}, {7, 10}, {9, 12}, {9, 10}, {11, 12}};

        // Known best networks up to size 16 for a full sort from
        // https://pages.ripco.net/~jgamble/nw.html

        // Warning:
        // https://www.angelfire.com/blog/ronz/Articles/999SortingNetworksReferen.html
        // has a bug in one of the networks. Don't use it.
        optimal[{9, 0, 8, false}] = {{0, 1}, {3, 4}, {6, 7}, {1, 2}, {4, 5}, {7, 8}, {0, 1}, {3, 4}, {6, 7}, {2, 5}, {0, 3}, {1, 4}, {5, 8}, {3, 6}, {4, 7}, {2, 5}, {0, 3}, {1, 4}, {5, 7}, {2, 6}, {1, 3}, {4, 6}, {2, 4}, {5, 6}, {2, 3}};
        optimal[{10, 0, 9, false}] = {{4, 9}, {3, 8}, {2, 7}, {1, 6}, {0, 5}, {1, 4}, {6, 9}, {0, 3}, {5, 8}, {0, 2}, {3, 6}, {7, 9}, {0, 1}, {2, 4}, {5, 7}, {8, 9}, {1, 2}, {4, 6}, {7, 8}, {3, 5}, {2, 5}, {6, 8}, {1, 3}, {4, 7}, {2, 3}, {6, 7}, {3, 4}, {5, 6}, {4, 5}};
        optimal[{11, 0, 10, false}] = {{0, 1}, {2, 3}, {4, 5}, {6, 7}, {8, 9}, {1, 3}, {5, 7}, {0, 2}, {4, 6}, {8, 10}, {1, 2}, {5, 6}, {9, 10}, {0, 4}, {3, 7}, {1, 5}, {6, 10}, {4, 8}, {5, 9}, {2, 6}, {0, 4}, {3, 8}, {1, 5}, {6, 10}, {2, 3}, {8, 9}, {1, 4}, {7, 10}, {3, 5}, {6, 8}, {2, 4}, {7, 9}, {5, 6}, {3, 4}, {7, 8}};
        optimal[{12, 0, 11, false}] = {{0, 1}, {2, 3}, {4, 5}, {6, 7}, {8, 9}, {10, 11}, {1, 3}, {5, 7}, {9, 11}, {0, 2}, {4, 6}, {8, 10}, {1, 2}, {5, 6}, {9, 10}, {0, 4}, {7, 11}, {1, 5}, {6, 10}, {3, 7}, {4, 8}, {5, 9}, {2, 6}, {0, 4}, {7, 11}, {3, 8}, {1, 5}, {6, 10}, {2, 3}, {8, 9}, {1, 4}, {7, 10}, {3, 5}, {6, 8}, {2, 4}, {7, 9}, {5, 6}, {3, 4}, {7, 8}};
        optimal[{13, 0, 12, false}] = {{1, 7}, {9, 11}, {3, 4}, {5, 8}, {0, 12}, {2, 6}, {0, 1}, {2, 3}, {4, 6}, {8, 11}, {7, 12}, {5, 9}, {0, 2}, {3, 7}, {10, 11}, {1, 4}, {6, 12}, {7, 8}, {11, 12}, {4, 9}, {6, 10}, {3, 4}, {5, 6}, {8, 9}, {10, 11}, {1, 7}, {2, 6}, {9, 11}, {1, 3}, {4, 7}, {8, 10}, {0, 5}, {2, 5}, {6, 8}, {9, 10}, {1, 2}, {3, 5}, {7, 8}, {4, 6}, {2, 3}, {4, 5}, {6, 7}, {8, 9}, {3, 4}, {5, 6}};
        optimal[{14, 0, 13, false}] = {{0, 1}, {2, 3}, {4, 5}, {6, 7}, {8, 9}, {10, 11}, {12, 13}, {0, 2}, {4, 6}, {8, 10}, {1, 3}, {5, 7}, {9, 11}, {0, 4}, {8, 12}, {1, 5}, {9, 13}, {2, 6}, {3, 7}, {0, 8}, {1, 9}, {2, 10}, {3, 11}, {4, 12}, {5, 13}, {5, 10}, {6, 9}, {3, 12}, {7, 11}, {1, 2}, {4, 8}, {1, 4}, {7, 13}, {2, 8}, {5, 6}, {9, 10}, {2, 4}, {11, 13}, {3, 8}, {7, 12}, {6, 8}, {10, 12}, {3, 5}, {7, 9}, {3, 4}, {5, 6}, {7, 8}, {9, 10}, {11, 12}, {6, 7}, {8, 9}};
        optimal[{15, 0, 14, false}] = {{0, 1}, {2, 3}, {4, 5}, {6, 7}, {8, 9}, {10, 11}, {12, 13}, {0, 2}, {4, 6}, {8, 10}, {12, 14}, {1, 3}, {5, 7}, {9, 11}, {0, 4}, {8, 12}, {1, 5}, {9, 13}, {2, 6}, {10, 14}, {3, 7}, {0, 8}, {1, 9}, {2, 10}, {3, 11}, {4, 12}, {5, 13}, {6, 14}, {5, 10}, {6, 9}, {3, 12}, {13, 14}, {7, 11}, {1, 2}, {4, 8}, {1, 4}, {7, 13}, {2, 8}, {11, 14}, {5, 6}, {9, 10}, {2, 4}, {11, 13}, {3, 8}, {7, 12}, {6, 8}, {10, 12}, {3, 5}, {7, 9}, {3, 4}, {5, 6}, {7, 8}, {9, 10}, {11, 12}, {6, 7}, {8, 9}};
        optimal[{16, 0, 15, false}] = {{0, 1}, {2, 3}, {4, 5}, {6, 7}, {8, 9}, {10, 11}, {12, 13}, {14, 15}, {0, 2}, {4, 6}, {8, 10}, {12, 14}, {1, 3}, {5, 7}, {9, 11}, {13, 15}, {0, 4}, {8, 12}, {1, 5}, {9, 13}, {2, 6}, {10, 14}, {3, 7}, {11, 15}, {0, 8}, {1, 9}, {2, 10}, {3, 11}, {4, 12}, {5, 13}, {6, 14}, {7, 15}, {5, 10}, {6, 9}, {3, 12}, {13, 14}, {7, 11}, {1, 2}, {4, 8}, {1, 4}, {7, 13}, {2, 8}, {11, 14}, {5, 6}, {9, 10}, {2, 4}, {11, 13}, {3, 8}, {7, 12}, {6, 8}, {10, 12}, {3, 5}, {7, 9}, {3, 4}, {5, 6}, {7, 8}, {9, 10}, {11, 12}, {6, 7}, {8, 9}};
    }

    if (use_superoptimized_leaves) {
        auto it = optimal.find({size, min_idx, max_idx, sorted_pairwise});
        if (it != optimal.end()) {
            //printf("Using superoptimized network for %d %d %d %d\n", size, min_idx, max_idx, -((int)sorted_pairwise));
            return it->second;
        } else if (size < 12 &&
                   (min_idx > 0 || max_idx < size - 1) &&
                   (min_idx < size - 1) &&
                   (max_idx > 0) &&
                   !already_optimal.count({size, min_idx, max_idx, sorted_pairwise})) {
            // Leave ourselves a TODO for superoptimization
            //printf("SUPEROPTIMIZE ME: %d %d %d %d\n", size, min_idx, max_idx, -((int)sorted_pairwise));
        }
    }

    // With superoptimized cases out of the way, we always want to
    // start by pairwise sorting
    vector<pair<int, int>> swaps;

    if (!sorted_pairwise) {
        for (int i = 0; i < size - 1; i += 2) {
            swaps.emplace_back(i, i + 1);
        }
    }
    sorted_pairwise = true;

    // Handle min and max networks with an early-out. We also know the
    // O(n) optimal solution for top-2 and bottom-2 networks.
    if (max_idx <= 1) {
        for (int i = 2; i < size; i += 2) {
            // Take the min of the min of each pair, and the last
            // element (which may not belong to a pair).
            swaps.emplace_back(0, i);
        }
        if (max_idx == 1) {
            // Take the min of what remains
            for (int i = 2; i < size; i++) {
                swaps.emplace_back(1, i);
            }
        }
        return swaps;
    }
    if (min_idx >= size - 2) {
        for (int i = 1; i < size - 1; i += 2) {
            // Take the max of the max of each pair and the last
            // element (which may not belong to a pair).
            swaps.emplace_back(i, size - 1);
        }
        if (min_idx == size - 2) {
            // Take the max of what remains
            for (int i = 0; i < size - 2; i++) {
                swaps.emplace_back(i, size - 2);
            }
        }
        return swaps;
    }

    // Now do the recursive step.

    // Sort the min of each pair. Figuring out the right min_idx and
    // max_idx takes some care, but it's the magic that makes pairwise
    // networks better for selection (according to Moshe Zazon-Ivry
    // and Michael Codish)

    // The element at min_idx in the final result is less than or
    // equal to (size - min_idx) values (including itself). Anything
    // <= more values than this is going to appear before min_idx, and
    // we don't care about it.
    int min_threshold = size - min_idx;

    // The element at max_idx in the final result is greater than or
    // equal to max_idx + 1 values (including itself). Anything >=
    // more values than this can similarly be discarded.
    int max_threshold = max_idx + 1;

    // It's now possible to do the math to figure out what the right
    // min_idx and max_idx in the subsorts is in closed form, but I
    // find it very confusing and prone to off-by-one errors,
    // especially for odd size. Let's just count.

    // Approximately divide the list into two
    int size_mins = (size + 1) / 2;
    int size_maxes = size / 2;

    int min_idx_in_mins = size_mins;
    int max_idx_in_mins = -1;

    int min_idx_in_maxes = size_maxes;
    int max_idx_in_maxes = -1;

    for (int i = 0; i < (size + 1) / 2; i++) {
        // Once we sort the list of mins, element i is <= itself and
        // everything after it, and the same number of elements in the
        // list of maxes. Except the list of maxes might be one shorter.
        int le_mins = (size_mins - i) + (size_maxes - i);
        // Note that this is just (size - 2 * i)

        // In the of maxes, element i is <= itself and everything
        // after it in that list only.
        int le_maxes = (size_maxes - i);

        // In the list of mins, elements i is >= itself and everything
        // before it.
        int ge_mins = i + 1;

        // In the list of maxes, element i is >= itself and everything
        // before it, and the same set of elements in the list of
        // mins.
        int ge_maxes = 2 * (i + 1);

        if (i < size_mins && le_mins <= min_threshold && ge_mins <= max_threshold) {
            // When sorting the list of mins, we might need this element
            min_idx_in_mins = std::min(i, min_idx_in_mins);
            max_idx_in_mins = std::max(i, max_idx_in_mins);
        }
        if (i < size_maxes && le_maxes <= min_threshold && ge_maxes <= max_threshold) {
            // When sorting the list of maxes, we might need this element
            min_idx_in_maxes = std::min(i, min_idx_in_maxes);
            max_idx_in_maxes = std::max(i, max_idx_in_maxes);
        }
    }

    if (min_idx_in_mins <= max_idx_in_mins) {
        auto swaps_mins = pairwise_sort(size_mins, min_idx_in_mins, max_idx_in_mins, false, use_superoptimized_leaves);
        for (auto &p : swaps_mins) {
            // Fix the wire ids
            p.first *= 2;
            p.second *= 2;
        }
        swaps.insert(swaps.end(), swaps_mins.begin(), swaps_mins.end());
    }
    if (min_idx_in_maxes <= max_idx_in_maxes) {
        auto swaps_maxes = pairwise_sort(size_maxes, min_idx_in_maxes, max_idx_in_maxes, false, use_superoptimized_leaves);
        for (auto &p : swaps_maxes) {
            // Fix the wire ids
            p.first *= 2;
            p.first++;
            p.second *= 2;
            p.second++;
        }

        swaps.insert(swaps.end(), swaps_maxes.begin(), swaps_maxes.end());
    }

    // Now we do the merge step common to both the even-odd merge and
    // also the pairwise sorting network.
    auto merge_swaps = pairwise_merge(size, min_idx, max_idx);
    swaps.insert(swaps.end(), merge_swaps.begin(), merge_swaps.end());

    return swaps;
}