#include <iostream>
#include <vector>
#include <tuple>
#include <map>
#include <queue>
#include <algorithm>
#include <functional>
#include <thread>
#include <mutex>
#include <atomic>
#include <memory>
#include <chrono>
using namespace std;

// Structura Union-Find pentru Kruskal
class UnionFind
{
public:
    vector<int> parent, rank;

    UnionFind(int n)
    {
        parent.resize(n + 1);
        rank.resize(n + 1, 0);
        for (int i = 0; i <= n; i++)
        {
            parent[i] = i;
        }
    }

    int find(int x)
    {
        if (parent[x] != x)
        {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    bool unite(int x, int y)
    {
        int px = find(x);
        int py = find(y);
        if (px == py)
            return false;

        if (rank[px] < rank[py])
        {
            parent[px] = py;
        }
        else if (rank[px] > rank[py])
        {
            parent[py] = px;
        }
        else
        {
            parent[py] = px;
            rank[px]++;
        }
        return true;
    }
};

// Functie pentru a numara toate APM-urile unui graf
long long countMSTs(int n, vector<pair<int, int>> &edges)
{
    // Atribuim cost 1 tuturor muchiilor pentru a avea mai multe APM-uri posibile
    vector<tuple<int, int, int>> weightedEdges;
    for (int i = 0; i < (int)edges.size(); i++)
    {
        weightedEdges.push_back(make_tuple(1, edges[i].first, edges[i].second));
    }

    // Grupam muchiile dupa cost
    map<int, vector<pair<int, int>>> edgesByWeight;
    for (auto &edge : weightedEdges)
    {
        int w = get<0>(edge);
        int u = get<1>(edge);
        int v = get<2>(edge);
        edgesByWeight[w].push_back(make_pair(u, v));
    }

    // Numaram APM-urile folosind backtracking pe muchiile cu acelasi cost
    function<long long(UnionFind &, vector<pair<int, int>> &, int, int)> countAPMs;
    countAPMs = [&](UnionFind &uf, vector<pair<int, int>> &sameWeightEdges, int idx, int neededEdges) -> long long
    {
        if (neededEdges == 0)
            return 1;
        if (idx >= (int)sameWeightEdges.size())
            return 0;

        long long count = 0;
        int u = sameWeightEdges[idx].first;
        int v = sameWeightEdges[idx].second;

        // Incercam sa nu adaugam aceasta muchie
        count += countAPMs(uf, sameWeightEdges, idx + 1, neededEdges);

        // Incercam sa adaugam aceasta muchie
        if (uf.find(u) != uf.find(v))
        {
            UnionFind newUf = uf;
            newUf.unite(u, v);
            count += countAPMs(newUf, sameWeightEdges, idx + 1, neededEdges - 1);
        }

        return count;
    };

    // Pentru simplitate, toate muchiile au cost 1
    // Numarul de APM-uri = numarul de moduri de a alege n-1 muchii care formeaza un arbore
    UnionFind uf(n);
    long long totalMSTs = countAPMs(uf, edgesByWeight[1], 0, n - 1);

    return totalMSTs;
}

// Functie pentru a verifica daca un graf este conex
bool isConnected(int n, vector<pair<int, int>> &edges)
{
    // Cream lista de adiacenta
    vector<vector<int>> adj(n + 1);
    for (auto &edge : edges)
    {
        adj[edge.first].push_back(edge.second);
        adj[edge.second].push_back(edge.first);
    }

    // BFS pentru a verifica conexitatea
    vector<bool> visited(n + 1, false);
    queue<int> q;
    q.push(1);
    visited[1] = true;
    int visitedCount = 1;

    while (!q.empty())
    {
        int node = q.front();
        q.pop();

        for (size_t i = 0; i < adj[node].size(); i++)
        {
            int neighbor = adj[node][i];
            if (!visited[neighbor])
            {
                visited[neighbor] = true;
                q.push(neighbor);
                visitedCount++;
            }
        }
    }

    return visitedCount == n;
}

// Functie pentru a procesa un batch de grafuri
void processBatch(int n, vector<pair<int, int>> allEdges,
                  vector<vector<int>> selectors,
                  atomic<int> &graphCount,
                  atomic<int> &connectedGraphCount,
                  atomic<long long> &maxMSTs,
                  shared_ptr<vector<pair<int, int>>> bestGraph,
                  mutex &bestGraphMutex)
{
    long long localMaxMSTs = 0;
    vector<pair<int, int>> localBestGraph;

    for (size_t s = 0; s < selectors.size(); s++)
    {
        vector<int> &selector = selectors[s];
        graphCount++;

        // Extragem muchiile selectate pentru acest graf
        vector<pair<int, int>> selectedEdges;
        for (size_t i = 0; i < allEdges.size(); i++)
        {
            if (selector[i] == 1)
            {
                selectedEdges.push_back(allEdges[i]);
            }
        }

        // Verificam daca graful este conex
        if (isConnected(n, selectedEdges))
        {
            connectedGraphCount++;

            // Numaram APM-urile pentru acest graf
            long long numMSTs = countMSTs(n, selectedEdges);

            // Verificam daca are cele mai multe APM-uri local
            if (numMSTs > localMaxMSTs)
            {
                localMaxMSTs = numMSTs;
                localBestGraph = selectedEdges;
            }
        }
    }

    // Actualizam rezultatul global daca am gasit ceva mai bun
    if (localMaxMSTs > 0)
    {
        lock_guard<mutex> lock(bestGraphMutex);
        long long currentMax = maxMSTs.load();
        if (localMaxMSTs > currentMax)
        {
            maxMSTs = localMaxMSTs;
            *bestGraph = localBestGraph;
        }
    }
}

// Functie pentru a genera toate grafurile cu n noduri si m muchii (multithreaded)
void generateGraphs(int n, int m)
{
    int maxEdges = n * (n - 1) / 2;
    if (m > maxEdges)
    {
        cout << "Nu se pot genera grafuri cu " << m << " muchii pentru " << n << " noduri!" << endl;
        return;
    }

    vector<pair<int, int>> allEdges;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            allEdges.push_back(make_pair(i, j));
        }
    }

    vector<int> selector(allEdges.size(), 0);
    fill(selector.begin(), selector.begin() + m, 1);

    cout << "Generare combinatii..." << endl;
    vector<vector<int>> allSelectors;
    do
    {
        allSelectors.push_back(selector);
    } while (prev_permutation(selector.begin(), selector.end()));

    cout << "Total combinatii: " << allSelectors.size() << endl;
    cout << "Procesare cu multithreading..." << endl;

    atomic<int> graphCount(0);
    atomic<int> connectedGraphCount(0);
    atomic<long long> maxMSTs(0);
    auto bestGraph = make_shared<vector<pair<int, int>>>();
    mutex bestGraphMutex;

    unsigned int numThreads = thread::hardware_concurrency();
    if (numThreads == 0)
        numThreads = 4;

    cout << "Folosim " << numThreads << " thread-uri" << endl
         << endl;

    size_t batchSize = allSelectors.size() / numThreads;
    vector<thread> threads;

    auto startTime = chrono::high_resolution_clock::now();

    for (unsigned int i = 0; i < numThreads; i++)
    {
        size_t start = i * batchSize;
        size_t end = (i == numThreads - 1) ? allSelectors.size() : (i + 1) * batchSize;

        vector<vector<int>> batch(allSelectors.begin() + start, allSelectors.begin() + end);

        threads.emplace_back(processBatch, n, allEdges, batch,
                             ref(graphCount), ref(connectedGraphCount),
                             ref(maxMSTs), bestGraph, ref(bestGraphMutex));
    }

    for (size_t i = 0; i < threads.size(); i++)
    {
        threads[i].join();
    }

    auto endTime = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::seconds>(endTime - startTime);

    cout << "========================================" << endl;
    cout << "Total grafuri generate: " << graphCount << endl;
    cout << "Total grafuri conexe: " << connectedGraphCount << endl;
    cout << "Timp de executie: " << duration.count() << " secunde" << endl;
    cout << "========================================" << endl
         << endl;

    cout << "GRAFUL CU CELE MAI MULTE APM-URI:" << endl;
    cout << "Numar maxim de APM-uri: " << maxMSTs << endl;
    cout << "Muchii: ";
    for (size_t i = 0; i < bestGraph->size(); i++)
    {
        cout << "(" << (*bestGraph)[i].first << "," << (*bestGraph)[i].second << ") ";
    }
    cout << endl;
}

int main()
{
    int n = 7;  // numarul de noduri
    int m = 10; // numarul de muchii

    cout << "Generare grafuri CONEXE cu " << n << " noduri si " << m << " muchii" << endl;
    cout << "========================================" << endl
         << endl;

    generateGraphs(n, m);

    return 0;
}