#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, ��� ������� � ���?
/*
  ���� ��� ������� ����� ������ pair<int, int>, ��� � ������ ���� typedef
  ������ ������� �������� �������� �������, ������ - �� ���.
*/

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; // �� �������.
    /*
    ��� ������? �� ��� ������ ������ �����, �������� SREZ = ... ?
    ��� ��� �� � ����. �� �� ������ ���-�� ���������
    */
    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; // �����? ����� ������ �� ���� �����..
	
	/* ����� - � ������� �� ������, � ��������� �13: "������ �������� �� ���� ���������, � ����
	���-�� ���� ������ �� "������", �� ������ �� �� ������ �� "�����������", � ������� �������..."
	���� ����� �� �������, �� �����-�� ������� ��� ������� ����� ��������� �� �������������� ���,
	� ����� �� ����� �������.
	
	���������� �����: ��� ������������� ������ � myPair ������������ value, ���������� ��� ��
	MyCluster::updateEdge (� ������, �� ������ Updator, � ��� ��� ���� ��������? ��� ��� ��������?
	� �������� ��� ���� ��������, (jj, ii), �� ����, myPair.second-��� ������ �������������� ��������,
        � myPair.first - ������ ����, ������� ���-��� ����� �����������. ������� ���� ������ ������
	�� ���� ��������� �������� ���������, � ������ �� ����������� �������� �� myPair.second, ����
	���������� ��� "�������", ��� � �������� � ���� ������).
	*/
    }
};
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> // �������..:)
/* ������ ����������, � ������ ������� �� �����, Boost �� ����������� :) */
{
    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 -���� ���.
	    
	/*
	���, ��� ������ ������� exists, ������� ����������, ���������� �� ������� � vector-�
	� ��������� ��� ���� �� �������� � ���������, �� � "�������" �� �������
	*/
    }
};
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);//�������� ��� ����� "�����" ������.
	/*
	����� �� ������ ���. � ��� ���� �������, ������ ���������� value,
	� ��� ��� ������. ��� ���, Updator ���������� ���������� for_each,
	�� ����, ��� ������� ��������� ����� ���������� updateEdge(). ���
	�������� ��� - ��. ����.
	*/
        }
    }
};

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; // ?
    /*
    � ��� ������ ���������, � � �� ������ � �� ����� ������� �������� ������ �����,
    ��� ���� ���-�� ������� ����������? �� ��������� ����� do { ... } while(counter > 1)
    ���������� � ������� clusters ��� ������������ (��� ��������� ������ ��� ��������
    ���������, ��� ������ ������� ����������� - �� �� �������������� ������)
    */
    
    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;// ?
	/* � ���� ������� �������������� GCC, ��� "����� ���� �������������������� ��������" */

        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, �
                //� ������� ��� �������� �������� �������� � ��� ������ ����� �������
		/*
		���� ��� �������� ����� � ������� �������� ������ min (�.�., ������� �� ���� ������
		��������), � ��� �������, �� ������� ��������� ��� �����, ������� (� ���� ����� ���
		��� �� ������), ��...
		*/
		
                {
                    ii = i; jj = clusters[i].Edges[j].first; min = clusters[i].Edges[j].second;
                    //����� (��� ii,jj - �� �������) ����� ����������� ����� � ��� ��� �������.. ?
			
		    /* ... � ii ���������� ����� ��������, � ������� ��������� ������� �������, �
		    jj - �������� ������� �������� ����� � ���� �������� (��� ��� � ��� ����������?
		    ���������, ��� ����������, ��� ����� ����������� ����� ������� �� �������� 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] ��������� clusters[jj] */
	
        clusters[ii].sr = min;//� ��� ��� ���� �� �������
	/* � ����������, � ����� ������ ��� ��������� (��� ����� ����) */
	
        //������ � �������
	/*
	� ��� �������� �� ����... � ������� ���, ����, � EdgeUpdate ��� ����������... ��� ���:
	��������� �� ���� ������, � ��� ������� �� ��� ��������� ��, ��� ������ Updator-��, � ������:
	���� ������� �������, �� ��� ��� �����, ������� ��������� �� JJ ����� ������ ��������� �� II,
	��� �� ����� �� ������� ���������� �������� JJ, � �� ������ ������������� �� �����, �� � ����
	������ ����������.
	*/
        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;
}