#include "triangles.h"
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()

vector<vector<int> > solve(int n) {
    auto checkin = [&](Triangle tr, int a) {
        return compare({tr}, {{tr.i, tr.j, a}, {tr.j, tr.k, a}, {tr.i, tr.k, a}}) == 0;
    };


    int a = 0, b = 1, c = 2;
    while (true) {
        bool change = false;
        for (int i = 0; i < n; ++i) {
            if (i != a && i != b && i != c && checkin({a, b, c}, i)) {
                a = i;
                change = true;
                break;
            }
        }
        if (!change) {
            break;
        }
    }

    vector<int> conv = {a, b, c};
    set<int> nu;
    for (int i = 0; i < n; ++i) {
        nu.insert(i);
    }
    nu.erase(a);
    nu.erase(b);
    nu.erase(c);
    vector<vector<int> > ans = {{a, b, c}};
    while (!nu.empty()) {
        Triangle mn = {*nu.begin(), conv[0], conv[1]};
        int itcon = 1;
        for (int i: nu) {
            for (int j = 0; j < conv.size(); ++j) {
                int d = conv[j];
                int e = conv[(j + 1) % conv.size()];
                if (compare({mn}, {{d, e, i}}) > 0) {
                    mn = {d, e, i};
                    itcon = (j + 1) % conv.size();
                }
            }
        }
        vector<int> curconv = {};
        int cur = itcon;
        for (int i = 0; i < conv.size(); ++i) {
            int cur0 = conv[(cur + i - 1) % conv.size()];
            int cur1 = conv[(cur + i) % conv.size()];
            int cur2 = conv[(cur + i + 1) % conv.size()];
            if (compare({{mn.k, cur0, cur1}, {cur0, cur1, cur2}}, {{mn.k, cur2, cur1}, {mn.k, cur2, cur0}}) == 0) {
                ans.push_back({mn.k, cur1, cur2});
            } else {
                curconv.push_back(conv[cur1]);
            }
        }
        conv = curconv;
        nu.erase(mn.k);
    }

    return ans;
}
