#include "triangles.h"

#include <algorithm>
#include <unordered_set>
using namespace std;

vector<vector<int>> solve(int n) {
    Triangle res = {0, 1, 2};
    for (int i = 3; i < n; i++) {
        Triangle a = {i, res.j, res.k};
        Triangle b = {res.i, i, res.k};
        Triangle c = {res.i, res.j, i};
        if (compare({a}, {res}) == -1) res = a;
        if (compare({b}, {res}) == -1) res = b;
        if (compare({c}, {res}) == -1) res = c;
    }

    unordered_set<int> used = {res.i, res.j, res.k};
    vector<vector<int>> ans = {{res.i, res.j, res.k}};
    for (int i = 0; i < n; i++) {
        if (used.count(i) > 0) continue;
        used.insert(i);
        Triangle a = {i, res.j, res.k};
        Triangle b = {res.i, i, res.k};
        Triangle c = {res.i, res.j, i};

        int chosen = -1;
        if (compare({a}, {res}) == 1) {
            res = a;
            chosen = 1;
        }
        if (compare({b}, {res}) == 1) {
            res = b;
            chosen = 2;
        }
        if (compare({c}, {res}) == 1) {
            res = c;
            chosen = 3;
        }
        if (chosen == 1) {
            ans.push_back({i, res.i, res.j});
            ans.push_back({i, res.i, res.k});
        } else if (chosen == 2) {
            ans.push_back({i, res.j, res.k});
            ans.push_back({i, res.j, res.i});
        } else if (chosen == 3) {
            ans.push_back({i, res.k, res.i});
            ans.push_back({i, res.k, res.j});
        }
    }
    return ans;
}
