#include "triangles.h"

// std::vector<std::vector<int>> solve(int n) {
//     // Example of compare:
//     // Пример использования функции compare:
//     std::vector<Triangle> left = {Triangle(0, 1, 2)};
//     std::vector<Triangle> right = {Triangle(0, 1, 2)};
//     int compare_result = compare(left, right);
//     // compare_result should be equal to 0.
//     // compare_result будет равняться нулю, так как сравнивались одинаковые треугольники.
    
//     // Example of return:
//     // Пример возвращаемого значения:
//     std::vector<std::vector<int>> ans;
//     ans.push_back(std::vector<int>(n));
//     for (int i = 0; i < n; ++i) {
//         ans[0][i] = i;
//     }
//     return ans;
// }

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

using ll = long long;
using ld = long double;

#ifdef DBG
#define $(x) x
#else
#define $(x)
#endif

#define debug(x) $(cout << #x << " = " << x << endl)

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

constexpr int INF = 1e9 + 7;
constexpr ll LINF = 1e18 + 7;

int N;


array<int,3> norm(Triangle a) {
    int i = a.i;
    int j = a.j;
    int k = a.k;

    vector<int> v = {i, j, k};
    sort(all(v));
    return {v[0], v[1], v[2]};
}


map<pair<vector<array<int,3>>, vector<array<int,3>>>, int> mp; 
int mcompare(vector<Triangle> a, vector<Triangle> b) {
    vector<array<int,3>> at, bt;

    sort(all(at));
    sort(all(bt));
    if (at > bt) swap(at, bt);
    for (auto& t : a) at.push_back(norm(t));
    for (auto& t : b) bt.push_back(norm(t));
    if (mp.count({at, bt}) == 0) mp[{at, bt}] = compare(a, b);
    
    return mp[{at, bt}];
}


int ni(int i, int v) {
    i %= N - 1;
    return i + (v <= i);
}
bool is_inner(int v) {
    vector<Triangle> a = {Triangle(ni(0, v), ni(1, v ), ni(2, v))};
    vector<Triangle> b;
    for (int i = 0; i < N - 1; ++i) {
        b.push_back(Triangle(v, ni(i, v), ni(i + 1, v)));
    }

    return mcompare(a, b) == 0;
}


vector<vector<int>> solve4(int n) {
    N = n;

    int v = -1;
    for (int i = 0; i < n; ++i) {
        if (is_inner(i)) {
            v = i;
            break;
        }
    }

    vector<vector<int>> ans;
    if (v == -1) {
        vector<pair<int, int>> sg = {
            {0, 1},
            {0, 2},
            {1, 2},
        };

        vector<pair<int, int>> rg = {
            {2, 3},
            {1, 3},
            {0, 3},
        };


        int s1, s2;
        int c1, c2;

        int id = -1;
        for (auto [a, b] : sg) {
            id++;
            auto [c, d] = rg[id]; 

            int r = mcompare({{a, b, c}, {a, b, d}}, {{c, d, a}, {c, d, b}});
            if (r == 0) {
                s1 = a;
                s2 = b;
                c1 = c;
                c2 = d;
            }
        }

        ans = {{s1, s2, c1}, {s1, s2, c2}};
    } else { 
        for (int i = 0; i < n - 1; ++i) {
            ans.push_back({v, ni(i, v), ni(i + 1, v)});
        }
    }

    return ans;
}

bool is_edge(int a, int b, int d) {
    for (int i = 0; i < N; ++i) {
        if (i == a || i == b || i == d) continue;
        int r = mcompare({{a, b, d}, {a, b, i}}, {{d, i, a}, {d, i, b}}); 
        if (r == 0) return 0;
    }
    return 1;
}

bool s_edge(int a, int b, int d, int i) {
    int r = mcompare({{a, b, d}, {a, b, i}}, {{d, i, a}, {d, i, b}}); 
    if (r == 0) return 0;
    return 1;
}

vector<vector<int>> solve(int n) {
    N = n;

    if (n == 4) {
        return solve4(n);
    }

    vector<vector<int>> ans;
    
    vector<int> v(n - 2, 0);
    iota(all(v), 0);
    nth_element(v.begin(), v.begin() + 3, v.end(), [&](int a, int b) {
        return mcompare({{n - 1, n - 2, a}}, {{n - 1, n - 2, b}}) > 0;
    });

    vector<int> c(3);
    for (int i = 0; i < 3; ++i)  {
        debug(i);
        c[i] = v[i];
    }

    int a, b = 0;

    if (is_edge(c[0], c[1], c[2])) {
        a = c[0];
        b = c[1];
    } else if (is_edge(c[1], c[2], c[0])) {
        a = c[1];
        b = c[2];
    } else {
        a = c[0];
        b = c[2];
    }

    v.clear();

    if (a > b) swap(a, b);

    for (int i = 0; i < n; ++i) {
        if (a == i || b == i) continue;
        v.push_back(i);
    }
    debug(a << ' ' << b);

    sort(all(v), [&](int c, int d) {
        if (c == d) return false;
        return mcompare({{a, b, c}}, {{a, b, d}}) < 0;
    });

    for (int i = 0; i < n - 3; ++i) {
        int c = v[i];
        int d = v[i + 1];

        debug(c << ' ' << d);
        if (is_edge(a, c, b)) swap(a, b);
        ans.push_back({a, b, c});
        b = c;
    }
    ans.push_back({a, b, v.back()});

    
    return ans;
}
