#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>

#define BIG
// #define TEST

using namespace std;

#ifdef BIG
    const int matrixSize = 19;
#else
    const int matrixSize = 8;
#endif

    const std::string titles[matrixSize] =
    {
        "Langasovo", "Egorshino", "Orehovo", "Perm",
        "Voynovka", "Inskaya", "Omsk", "Ekaterinburg"

#ifdef BIG
        , "Berdyaush", "Smichka", "Chusovskaya", "Agriz",
        "NNov", "Yudino", "Chelyabinsk", "Bogdanovich",
        "KUral", "Kurgan", "Altaiskaya"
#endif
    };

typedef std::pair<int, int> Rec;//пара для координат вершины , i-j, или вершина и вес?

class MyCluster
{
    friend std::ostream& operator << (std::ostream&, MyCluster&);//оператор вывода кластера

    std::string get_vertexes();
    void print(ostream& os)
    {
        os << "Vertexes: " << get_vertexes() << endl;
        os << "SREZ = " << sr << endl;
        os << "Edges:" << endl;
        for(unsigned i = 0; i < Edges.size(); i++)
        {
            os << "(" << Edges[i].first << " " << Edges[i].second << ")" << endl;
        }
    }

    vector<int> vx;// список вершин, видимо?

public:
    int sr;//не понятно.
    bool disabled;//является ли активным или задизейблен
    vector<Rec> Edges;//ребра

    MyCluster(int vertex): sr(0), disabled(false)
    {
        vx.push_back(vertex);//при создании вершины,записываем её себе
    }

    void updateEdge(Rec);
    void addEdge(Rec where)
    {
        Edges.push_back(where);//добовляем ребро
    }

    void operator += (MyCluster&);
};

// friend functions
std::ostream& operator << (std::ostream& os, MyCluster& cluster)//выводим наш кластер
{
    cluster.print(os);
    return os;
}


class EdgeUpdate {//класс обдейтер для ребра
public:
    Rec myPair;//ребрышко на апдейт
    EdgeUpdate(const Rec &value): myPair(value) {
    }

    void operator() (Rec& edge) const {//сам метод обновления
        if(edge.first == myPair.first) edge.first = myPair.second;//если 1ая вершина в пришедней паре==
            //1ой вершине "моей" паре, тогда мы меняем вершину 1 на вершину 2..
        //зачем? может дальше по коду пойму..
    }
};
void MyCluster::updateEdge(Rec myPair)
{
    for_each(Edges.begin(), Edges.end(), EdgeUpdate(myPair));//обновить все свои вершины..
    //для чего??
}

std::string MyCluster::get_vertexes()//вернем имена вершин
{
    std::string res = "";
    for(unsigned i = 0; i < vx.size(); i++)
    {
        res += titles[vx[i]] + " ";
    }
    return res;
}

struct Xists: public binary_function<int, vector<int>, bool>// страшно..:)
{
    bool operator() (const int& value, vector<int> vec) const
    {
        vector<int>::const_iterator it = std::find(vec.begin(), vec.end(), value);//ищет в векторе вершину?
        return (it != vec.end()) ? true : false;//true - если нашел, false -если нет.
    }
};
struct finder: std::binary_function< Rec, vector<int>, bool >
{
    bool operator() (Rec const& in, vector<int> vec) const
    {
        return Xists()(in.first, vec);//ищем тут первую коориднату вершины в векторе?
    }
};


void MyCluster :: operator += (MyCluster& cL)//ну тут аналог QSet.intersect, только для вектора ?
{
    // 0 добавляем неповторяющиеся значения из cL.vx в this->vx
    remove_copy_if(cL.vx.begin(), cL.vx.end(), back_inserter(vx), bind2nd(Xists(), vx));
    // 1 добавляем cL.Edges в конец Edges
    copy(cL.Edges.begin(), cL.Edges.end(), back_inserter(Edges));
    // 2 удаляем все те элементы из Edges, которые удовлетворяют
    // условию, записанному в finder
    Edges.erase(remove_if(Edges.begin(), Edges.end(), bind2nd(finder(), vx)),
                Edges.end());
}

class Updator {//апдейтер ребер?
private:
    Rec myPair;
public:
    Updator(const Rec& value) : myPair(value) {
    }
    void operator() (MyCluster& cluster) const {
        if(!cluster.disabled) {//если кластер активен
            cluster.updateEdge(myPair);//обновить его ребра "своим" ребром.
        }
    }
};

bool IsEnabled(const MyCluster& cluster)
{
    return (cluster.disabled == false);//проверяем на активность
}

int main()
{
    int dm[matrixSize][matrixSize] =
    {
        #ifdef BIG
{   0, 177, 171, 642, 981,  15, 403,1315, 689,1119, 311,1201, 420,1103, 595, 930,  89, 311,1020},
{ 177,   0, 348, 465, 804, 192, 226,1138, 866, 942, 134,1024, 243, 926, 772, 753,  88, 134,1197},
{ 171, 348,   0, 813,1152, 156, 574,1486, 518,1290, 482,1372, 591,1274, 424,1101, 260, 482, 849},
{ 642, 465, 813,   0, 339, 657, 239, 673,1331, 477, 331, 559, 222, 461,1237, 288, 553, 331,1662},
{ 981, 804,1152, 339,   0, 996, 578, 334,1670, 138, 670, 220, 561, 122,1576,  51, 892, 670,2001},
{  15, 192, 156, 657, 996,   0, 418,1330, 674,1134, 326,1216, 435,1118, 580, 945, 104, 326,1005},
{ 403, 226, 574, 239, 578, 418,   0, 912,1092, 716,  92, 798,  17, 700, 998, 527, 314,  92,1423},
{1315,1138,1486, 673, 334,1330, 912,   0,2004, 196,1004, 114, 895, 212,1910, 385,1226,1004,2335},
{ 689, 866, 518,1331,1670, 674,1092,2004,   0,1808,1000,1890,1109,1792,  94,1619, 778,1000, 331},
{1119, 942,1290, 477, 138,1134, 716, 196,1808,   0, 808,  82, 699,  16,1714, 189,1030, 808,2139},
{ 311, 134, 482, 331, 670, 326,  92,1004,1000, 808,   0, 890, 109, 792, 906, 619, 222,   0,1331},
{1201,1024,1372, 559, 220,1216, 798, 114,1890,  82, 890,   0, 781,  98,1796, 271,1112, 890,2221},
{ 420, 243, 591, 222, 561, 435,  17, 895,1109, 699, 109, 781,   0, 683,1015, 510, 331, 109,1440},
{1103, 926,1274, 461, 122,1118, 700, 212,1792,  16, 792,  98, 683,   0,1698, 173,1014, 792,2123},
{ 595, 772, 424,1237,1576, 580, 998,1910,  94,1714, 906,1796,1015,1698,   0,1525, 684, 906, 425},
{ 930, 753,1101, 288,  51, 945, 527, 385,1619, 189, 619, 271, 510, 173,1525,   0, 841, 619,1950},
{  89,  88, 260, 553, 892, 104, 314,1226, 778,1030, 222,1112, 331,1014, 684, 841,   0, 222,1109},
{ 311, 134, 482, 331, 670, 326,  92,1004,1000, 808,   0, 890, 109, 792, 906, 619, 222,   0,1331},
{1020,1197, 849,1662,2001,1005,1423,2335, 331,2139,1331,2221,1440,2123, 425,1950,1109,1331,   0}
        #else
        {    0,  177,  171, 642,  981,   15, 403, 1315 },
        {  177,    0,  348, 465,  804,  192, 226, 1138 },
        {  171,  348,    0, 813, 1152,  156, 574, 1486 },
        {  642,  465,  813,   0,  339,  657, 239,  673 },
        {  981,  804, 1152, 339,    0,  996, 578,  334 },
        {   15,  192,  156, 657,  996,    0, 418, 1330 },
        {  403,  226,  574, 239,  578,  418,   0,  912 },
        { 1315, 1138, 1486, 673,  334, 1330, 912,    0 }
        #endif
    }; // матрица смежности графа

    int sm[matrixSize][matrixSize];//матрица МОД
    int used[matrixSize];//использованные вершины
    int count=0;
    int min;

    for (int i=0; i< matrixSize; ++i)//Алгоритм прима.
    {
        used[i]=0;
        for(int j=0;j< matrixSize;++j) sm[i][j]=0;
    }

    used[0]=1;
    int idx;
    do
    {
        min=std::numeric_limits<int>::max();
        for(int i=0;i<matrixSize;++i)
        {
            if (used[i]!=0)
            {
                for(int j=0;j<matrixSize;++j)
                    if ( (dm[j][i] < min) && (dm[j][i]!=0) && (used[j]==0))
                    {
                        min=dm[j][i]; idx = j;
                    }
            }
        }

        for(int i=0;i < matrixSize;++i)
            for(int j=0;j<matrixSize;++j)
                if( (dm[j][i]== min) && (used[j]==0) &&(used[i]==1))
                {
                    used[j] =1;
                    sm[j][i]= sm[i][j] = min;
                    count++;
                    i=matrixSize;
                    break;
                }
    }
    while(count < matrixSize-1);

    // Выводим матрицу МОД ...
    for(int i = 0; i < matrixSize; i++)
    {
        for(int j = 0; j < matrixSize; j++)
        {
            std::cout << sm[i][j] << " ";
        }
        std::cout << std::endl;
    }
/* **** */
    vector<MyCluster> clusters;//вектор кластеров/вершин

    for(int i = 0; i < matrixSize; i++)
    {
        clusters.push_back(MyCluster(i));//создаем вершинки
    }

    vector<MyCluster> res;// ?
    for(int i = 0; i < matrixSize; i++)
        for(int j = 0; j < matrixSize; j++)
        {
            if(sm[i][j] > 0)
            {
                clusters[i].addEdge(make_pair(j, sm[i][j]));//создаем ребра
            }
        }

    int counter;//счетчик?
    do
    {
        int ii = -1, jj = -1;// ?
        min = std::numeric_limits<int>::max();//
        for(int i = 0; i < matrixSize; i++)//ищем мин. ребром
        {
            if(clusters[i].disabled) continue;//если кластер задизейбленый, поскакиваем этот шаг
            for(unsigned j = 0; j < clusters[i].Edges.size(); j++)
            {
                if((clusters[i].Edges[j].second < min) && (clusters[clusters[i].Edges[j].first].disabled == false))
                //если текущий кластер и его текущего ребро,..и тут видимо в second вес?? <min, и
                //и кластер под индексом текущего кластера и его номера ребра активен
                {
                    ii = i; jj = clusters[i].Edges[j].first; min = clusters[i].Edges[j].second;
                    //тогда (про ii,jj - не понятно) тогда минимальнео ребро у нас это текущее.. ?
                }
            }

        }

        #ifdef TEST
            cout << "test: min = " << min << " ii = " << ii << " jj = " << jj << endl;
            cout << clusters[ii] << endl << clusters[jj] << endl;
        #endif

        clusters[ii] += clusters[jj];//соединяем вершины????
        clusters[ii].sr = min;//и вот это тоже не понятно
        //дальше я теряюсь
        for_each(clusters.begin(), clusters.end(), Updator(make_pair(jj, ii)));//для кажого кластера/вершины
        //в векторе кластеров обновить его ребра на jj,ii кооридинаты..не понятно в общем.

        clusters[jj].disabled = true;//jj кластер убран
        res.push_back(clusters[ii]);//в резалт добовляем кластер ii

        #ifdef TEST
            cout << "result = " << endl << clusters[ii];
            cin.get();
        #endif

        counter = count_if(clusters.begin(), clusters.end(), IsEnabled);//получаем количество активных вершин
        #ifdef TEST
            cout << "Counter = " << counter << endl;
        #endif
    }
    while(counter > 1);//до тех по, пока количество активных вершин более 1

    std::cout << res.size() << std::endl;
    std::vector<MyCluster>::iterator it;
    for(it = res.begin(); it != res.end(); it++)
    {
        cout << *it << endl << endl << endl;//ну и выводим, видимо, наши кластера...
    }
    return 0;
}