#include "triangles.h"
#include <algorithm>
#include <vector>

std::vector<std::vector<int>> solve(int n) {
    std::vector<int> freed;
    std::vector<std::vector<int>> ans;

    for (int i = 0; i < n; ++i) freed.push_back(i);
    while (freed.size() > 3) {
        Triangle bst = {freed[0], freed[1], freed[2]};
        bool flag = true;
        while (flag) {
            flag = false;
            for (int const &i : freed) {
                if (bst.i == i or bst.j == i or bst.k == i) continue;
                Triangle cur = {i, bst.j, bst.k};
                if (compare({cur}, {bst}) == -1) {
                    bst = cur;
                    flag = true;
                } else {
                    cur = {bst.i, i, bst.k};
                    if (compare({cur}, {bst}) == -1) {
                        bst = cur;
                        flag = true;
                    } else {
                        cur = {bst.i, bst.j, i};
                        if (compare({cur}, {bst}) == -1) {
                            bst = cur;
                            flag = true;
                        }
                    }
                }
            }
        }

        int t = 0;
        while (freed[t] == bst.i or freed[t] == bst.j or freed[t] == bst.k) ++t;
        t = freed[t];
        std::vector<int> p{std::min({bst.i, bst.j, bst.k}), bst.i + bst.j + bst.k - std::min({bst.i, bst.j, bst.k}) - std::max({bst.i, bst.j, bst.k}), std::max({bst.i, bst.j, bst.k})};
        do {
            if (compare({{p[0], p[1], p[2]}, {p[0], p[2], t}}, {{p[0], p[1], t}, {p[1], p[2], t}}) == 0) {
                break;
            }
        } while (std::next_permutation(p.begin(), p.end()));

        ans.push_back({p[0], p[1], p[2]});
        for (int i = 0; i < freed.size(); ++i) {
            if (freed[i] == p[1]) {
                std::swap(freed[i], freed.back());
                freed.pop_back();
                break;
            }
        }
    }
    ans.push_back(freed);
    return ans;
}
