#include <iostream>
#include <vector>
#include "Sampler.h"
#include "DisjointSet.h"

using namespace std;

const uint32_t
    neighbors[31][4] =
        {
                { 0, 0, 0, 0},

                { 2, 5, 6,10},
                { 1, 3, 6, 7},
                { 2, 4, 7, 8},
                { 3, 5, 8, 9},
                { 1, 4, 9,10},

                { 1, 2,11,20},
                { 2, 3,12,13},
                { 3, 4,14,15},
                { 4, 5,16,17},
                { 1, 5,18,19},

                { 6,12,20,21},
                { 7,11,13,21},
                { 7,12,14,22},
                { 8,13,15,22},
                { 8,14,16,23},

                { 9,15,17,23},
                { 9,16,18,24},
                {10,17,19,24},
                {10,18,20,25},
                { 6,19,11,25},

                {11,12,26,27},
                {13,14,27,28},
                {15,16,28,29},
                {17,18,29,30},
                {19,20,26,30},

                {27,30,21,25},
                {26,28,21,22},
                {27,29,22,23},
                {28,30,23,24},
                {29,26,24,25}
        },
        rotations[31][31] = {
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30},
        {0, 2, 3, 4, 5, 1, 7, 8, 9, 10, 6, 13, 14, 15, 16, 17, 18, 19, 20, 11, 12, 22, 23, 24, 25, 21, 27, 28, 29, 30, 26},
        {0, 3, 4, 5, 1, 2, 8, 9, 10, 6, 7, 15, 16, 17, 18, 19, 20, 11, 12, 13, 14, 23, 24, 25, 21, 22, 28, 29, 30, 26, 27},
        {0, 4, 5, 1, 2, 3, 9, 10, 6, 7, 8, 17, 18, 19, 20, 11, 12, 13, 14, 15, 16, 24, 25, 21, 22, 23, 29, 30, 26, 27, 28},
        {0, 5, 9, 17, 18, 10, 4, 16, 24, 19, 1, 8, 15, 23, 29, 30, 25, 20, 6, 2, 3, 14, 28, 26, 11, 7, 13, 22, 27, 21, 12},
        {0, 6, 1, 10, 19, 20, 2, 5, 18, 25, 11, 3, 4, 9, 17, 24, 30, 26, 21, 12, 7, 8, 16, 29, 27, 13, 14, 15, 23, 28, 22},
        {0, 7, 2, 6, 11, 12, 3, 1, 20, 21, 13, 4, 5, 10, 19, 25, 26, 27, 22, 14, 8, 9, 18, 30, 28, 15, 16, 17, 24, 29, 23},
        {0, 8, 3, 7, 13, 14, 4, 2, 12, 22, 15, 5, 1, 6, 11, 21, 27, 28, 23, 16, 9, 10, 20, 26, 29, 17, 18, 19, 25, 30, 24},
        {0, 9, 17, 18, 10, 5, 16, 24, 19, 1, 4, 23, 29, 30, 25, 20, 6, 2, 3, 8, 15, 28, 26, 11, 7, 14, 22, 27, 21, 12, 13},
        {0, 10, 5, 9, 17, 18, 1, 4, 16, 24, 19, 2, 3, 8, 15, 23, 29, 30, 25, 20, 6, 7, 14, 28, 26, 11, 12, 13, 22, 27, 21},
        {0, 11, 20, 25, 26, 21, 6, 19, 30, 27, 12, 1, 10, 18, 24, 29, 28, 22, 13, 7, 2, 5, 17, 23, 14, 3, 4, 9, 16, 15, 8},
        {0, 12, 21, 27, 22, 13, 11, 26, 28, 14, 7, 20, 25, 30, 29, 23, 15, 8, 3, 2, 6, 19, 24, 16, 4, 1, 10, 18, 17, 9, 5},
        {0, 13, 12, 21, 27, 22, 7, 11, 26, 28, 14, 2, 6, 20, 25, 30, 29, 23, 15, 8, 3, 1, 19, 24, 16, 4, 5, 10, 18, 17, 9},
        {0, 14, 22, 28, 23, 15, 13, 27, 29, 16, 8, 12, 21, 26, 30, 24, 17, 9, 4, 3, 7, 11, 25, 18, 5, 2, 6, 20, 19, 10, 1},
        {0, 15, 14, 22, 28, 23, 8, 13, 27, 29, 16, 3, 7, 12, 21, 26, 30, 24, 17, 9, 4, 2, 11, 25, 18, 5, 1, 6, 20, 19, 10},
        {0, 16, 9, 4, 8, 15, 17, 5, 3, 14, 23, 18, 10, 1, 2, 7, 13, 22, 28, 29, 24, 19, 6, 12, 27, 30, 25, 20, 11, 21, 26},
        {0, 17, 18, 10, 5, 9, 24, 19, 1, 4, 16, 30, 25, 20, 6, 2, 3, 8, 15, 23, 29, 26, 11, 7, 14, 28, 27, 21, 12, 13, 22},
        {0, 18, 24, 30, 25, 19, 17, 29, 26, 20, 10, 16, 23, 28, 27, 21, 11, 6, 1, 5, 9, 15, 22, 12, 2, 4, 8, 14, 13, 7, 3},
        {0, 19, 18, 24, 30, 25, 10, 17, 29, 26, 20, 5, 9, 16, 23, 28, 27, 21, 11, 6, 1, 4, 15, 22, 12, 2, 3, 8, 14, 13, 7},
        {0, 20, 25, 26, 21, 11, 19, 30, 27, 12, 6, 18, 24, 29, 28, 22, 13, 7, 2, 1, 10, 17, 23, 14, 3, 5, 9, 16, 15, 8, 4},
        {0, 21, 27, 22, 13, 12, 26, 28, 14, 7, 11, 30, 29, 23, 15, 8, 3, 2, 6, 20, 25, 24, 16, 4, 1, 19, 18, 17, 9, 5, 10},
        {0, 22, 28, 23, 15, 14, 27, 29, 16, 8, 13, 26, 30, 24, 17, 9, 4, 3, 7, 12, 21, 25, 18, 5, 2, 11, 20, 19, 10, 1, 6},
        {0, 23, 15, 14, 22, 28, 16, 8, 13, 27, 29, 9, 4, 3, 7, 12, 21, 26, 30, 24, 17, 5, 2, 11, 25, 18, 10, 1, 6, 20, 19},
        {0, 24, 30, 25, 19, 18, 29, 26, 20, 10, 17, 28, 27, 21, 11, 6, 1, 5, 9, 16, 23, 22, 12, 2, 4, 15, 14, 13, 7, 3, 8},
        {0, 25, 26, 21, 11, 20, 30, 27, 12, 6, 19, 29, 28, 22, 13, 7, 2, 1, 10, 18, 24, 23, 14, 3, 5, 17, 16, 15, 8, 4, 9},
        {0, 26, 21, 11, 20, 25, 27, 12, 6, 19, 30, 22, 13, 7, 2, 1, 10, 18, 24, 29, 28, 14, 3, 5, 17, 23, 15, 8, 4, 9, 16},
        {0, 27, 22, 13, 12, 21, 28, 14, 7, 11, 26, 23, 15, 8, 3, 2, 6, 20, 25, 30, 29, 16, 4, 1, 19, 24, 17, 9, 5, 10, 18},
        {0, 28, 23, 15, 14, 22, 29, 16, 8, 13, 27, 24, 17, 9, 4, 3, 7, 12, 21, 26, 30, 18, 5, 2, 11, 25, 19, 10, 1, 6, 20},
        {0, 29, 24, 17, 16, 23, 30, 18, 9, 15, 28, 25, 19, 10, 5, 4, 8, 14, 22, 27, 26, 20, 1, 3, 13, 21, 11, 6, 2, 7, 12},
        {0, 30, 25, 19, 18, 24, 26, 20, 10, 17, 29, 21, 11, 6, 1, 5, 9, 16, 23, 28, 27, 12, 2, 4, 15, 22, 13, 7, 3, 8, 14}
    },
    mirror[31] = {
        0,1, 5,4,3,2,10,9,8,7,6,18,17,16,15,14,13,12,11,20,19,24,23,22,21,25,30,29,28,27,26
};

bool
    edges[31][4],
    used[31];

void visit(uint32_t v,vector<uint32_t> &s) {

    used[v] = true;

    for (uint32_t w=0;w<4;w++)
        if (edges[v][w] && !used[neighbors[v][w]])
            visit(neighbors[v][w],s);

    s.push_back(v);
}

int main() {
    Sampler
        sampler(120);
    DisjointSet
        ds(31);
    vector<uint32_t>
        section;
    uint32_t
        e,
        v1,v2;

    for (auto & whack : edges)
        whack[0] = whack[1] = whack[2] = whack[3] = false;
    for (auto & u : used)
        u = false;

    for (uint32_t i=0;i<27;) {
        e = sampler.getSample();

        v1 = 1 + e / 4;
        v2 = neighbors[v1][e%4];

//        cout << v1 << '-' << v2 << "   " << ds.dsFind(v1) << '-' << ds.dsFind(v2) << endl;

        if (ds.dsFind(v1) != ds.dsFind(v2) && !edges[v1][e%4]) {
//            cout << '+' << endl;
            edges[v1][e % 4] = true;
            for (uint32_t j=0;j<4;j++)
                if (neighbors[v2][j] == v1)
                    edges[v2][j] = true;

            ds.dsUnion(v1, v2);

            i++;
        }
    }

    for (uint32_t i=1;i<31;i++)
        if (!used[i]) {
            visit(i, section);
            cout << section.size();
            for (auto w: section)
                for (uint32_t j=1;j<31;j++)
                    if (rotations[section[0]][j] == w)
//                        cout << ' ' << (section.size() > 15 ? mirror[j] : j);
            cout << ' ' << j;
            cout << endl;

            section.clear();
        }

    return 0;
}