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

#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
    };

bool exists(std::vector<int> vec, int value)
{
    std::vector<int>::const_iterator it = std::find(vec.begin(), vec.end(), value);
    return (it != vec.end()) ? true : false;
}

class MyCluster
{
    friend std::ostream& operator << (std::ostream&, MyCluster&);
    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;
        }
    }
public:
    int sr;
    bool disabled;
    vector< pair<int, int> > Edges;
    vector<int> vx;
    MyCluster(int vertex)
    {
        sr = 0;
        disabled = false;
        vx.push_back(vertex);
    }

    void addEdge(pair<int, int> where)
    {
        Edges.push_back(where);
    }

    void operator += (MyCluster&);
    int edgesCount()
    {
        return Edges.size();
    }

    std::string get_vertexes();
};

std::ostream& operator << (std::ostream& os, MyCluster& cluster)
{
    cluster.print(os);
    return os;
}

std::string MyCluster::get_vertexes()
{
    std::string res = "";
    for(unsigned i = 0; i < vx.size(); i++)
    {
        res += titles[vx[i]] + " ";
    }
    return res;
}


void MyCluster :: operator += (MyCluster& cL)
{
    //
    for(unsigned i = 0; i < cL.vx.size(); i++)
    {
        if(!exists(vx, cL.vx[i]))
            vx.push_back(cL.vx[i]);
    }

    vector< pair<int, int> > copyEdges;
    for(unsigned i = 0; i < Edges.size(); i++)
    {
        if(!exists(vx, Edges[i].first))
            copyEdges.push_back(Edges[i]);
    }
    for(unsigned i = 0; i < cL.Edges.size(); i++)
    {
        if(!exists(vx, cL.Edges[i].first))
            copyEdges.push_back(cL.Edges[i]);
    }
    Edges.clear();
    // copy(copyEdges.begin(), copyEdges.end(), Edges.begin());
    copy(copyEdges.begin(), copyEdges.end(), back_inserter(Edges));
}

/*
class Cluster
{
    friend std::ostream& operator << (std::ostream&, Cluster&);
    friend Cluster* exists(std::vector<Cluster*>&, int);
    void print(std::ostream& os)
    {
        os << get_vertexes() << " SREZ = " << sr << std::endl;
    }

    std::vector<int> vx;
    std::vector<Cluster *> parents;
    int sr;

public:
    Cluster(int a, int b, int srez)
    {
        vx.push_back(a);
        vx.push_back(b);
        sr = srez;
    }
    Cluster(Cluster *first, int b, int srez)
    {
        vx.push_back(b);
        parents.push_back(first);
        sr = srez;
    }
    Cluster(Cluster *first, Cluster *second, int srez)
    {
        parents.push_back(first);
        parents.push_back(second);
        sr = srez;
    }

    std::string get_vertexes();
};
std::ostream& operator << (std::ostream& os, Cluster& cluster)
{
    cluster.print(os);
    return os;
}

std::string Cluster::get_vertexes()
{
    std::string res = "";
    for(unsigned i = 0; i < parents.size(); i++)
    {
        res += parents[i]->get_vertexes() + " ";
    }
    for(unsigned i = 0; i < vx.size(); i++)
    {
        res += titles[vx[i]] + " ";
    }
    return res;
}

Cluster* exists(std::vector<Cluster*> &cluster, int value)
{
    for(unsigned i = 0; i < cluster.size(); i++)
    {
        std::vector<int>::const_iterator it =
            std::find(cluster[i]->vx.begin(), cluster[i]->vx.end(), value);
        if(it != cluster[i]->vx.end()) return cluster[i];
    }
    return 0;
}

bool xist(std::vector<int> vec, int value)
{
    std::vector<int>::const_iterator it = std::find(vec.begin(), vec.end(), value);
    return (it != vec.end()) ? true : false;
}
*/

using namespace std;
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 n = matrixSize;
vector < pair < int, pair<int,int> > > g; // вес - вершина 1 - вершина 2
for(int i = 0; i < matrixSize; i++)
    for(int j = i + 1; j < matrixSize; j++)
    {
        if(dm[i][j] > 0)
        {
            g.push_back(make_pair(dm[i][j], make_pair(i, j)));
        }
    }
*/

/*
int cost = 0;
vector < pair<int,int> > res;

sort (g.begin(), g.end());
vector<int> tree_id (n);
for (int i=0; i<n; ++i)
	tree_id[i] = i;
int m = g.size();
for (int i=0; i<m; ++i)
{
	int a = g[i].second.first,  b = g[i].second.second,  l = g[i].first;
	if (tree_id[a] != tree_id[b])
	{
		cost += l;
		res.push_back (make_pair (a, b));
		int old_id = tree_id[b],  new_id = tree_id[a];
		for (int j=0; j<n; ++j)
			if (tree_id[j] == old_id)
				tree_id[j] = new_id;
	}
}
*/
/*
int cost = 0;
vector < pair<int,int> > res;
int m = g.size();

sort (g.begin(), g.end());
vector<int> p (n);
for (int i=0; i<n; ++i)
	p[i] = i;
for (int i=0; i<m; ++i)
{
	int a = g[i].second.first,  b = g[i].second.second,  l = g[i].first,  pa,  pb;
	for (pa=a; pa!=p[pa]; pa=p[pa]) ;
	for (pb=b; pb!=p[pb]; pb=p[pb]) ;
	for (int j=a; j!=p[j]; j=p[j])  p[j] = pa;
	for (int j=b; j!=p[j]; j=p[j])  p[j] = pb;
	if (pa != pb)
	{
		cost += l;
		res.push_back (g[i].second);
		if (rand() & 1)
			p[pb] = pa;
		else
			p[pa] = pb;
	}
}
for(unsigned i = 0; i < res.size(); i++)
{
    cout << res[i].first << ", " << res[i].second << endl;
}
*/

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

    // std::vector<int> mins;

    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)) // && !xist(mins, dm[j][i]))
                    {
                        min=dm[j][i]; idx = j;
                    }
            }
        }
        // mins.push_back(min);

        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;
    }

    MyCluster clusters[matrixSize] = {
        0, 1, 2, 3, 4, 5, 6, 7
        #ifdef BIG
            , 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18
        #endif
    };
    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]));
            }
        }

    for(;;)
    {
        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))
                {
                    ii = i; jj = clusters[i].Edges[j].first; min = clusters[i].Edges[j].second;
                }
            }

        }

//if(jj > -1) {
#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;
        // clusters[jj] = clusters[ii];

        // ***
        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].first == jj)
                {
                    clusters[i].Edges[j].first = ii;
                }
            }
        }
        // ***

        clusters[jj].disabled = true;
        res.push_back(clusters[ii]);
#ifdef TEST
        cout << "result = " << endl << clusters[ii];
        // cout << clusters[ii] << endl << endl;
        //cout << "Result cluster: " << endl;
        //cout << clusters[ii] << endl;
        cin.get();
#endif
//}

        int counter = 0;
        for(int i = 0; i < matrixSize; i++)
            // counter += clusters[i].edgesCount();
            if(!clusters[i].disabled) counter += 1;
#ifdef TEST
        cout << "Counter = " << counter << endl;
#endif
        if(counter == 1) break;
    }
    std::cout << res.size() << std::endl;
    std::vector<MyCluster>::iterator it;
    for(it = res.begin(); it != res.end(); it++)
    {
        cout << *it << endl << endl << endl;
    }

/*
    std::vector< std::pair<int, int> > mins;
    std::vector<Cluster*> clusters;
    int ii, jj;
    for(int cycle = 1; cycle < matrixSize; cycle++)
    {
        min = std::numeric_limits<int>::max();
        for(int i = 0; i < matrixSize; i++)
        {
            for(int j = i + 1; j < matrixSize; j++)
            {
                if(sm[i][j] > 0 && sm[i][j] < min)
                {
                    //if(sm[i][j] == min)
                    //{
                    //    mins.push_back(std::pair<int, int>(i, j));
                    //}
                    //else
                    //{
                        //mins.clear();
                        //mins.push_back(std::pair<int, int>(i, j));
                        //min = sm[i][j];
                        ii = i; jj = j;
                    //}

                }
            }
        }

        //for(unsigned i = 0; i < mins.size(); i++)
        //{
        //    int ii, jj;
        //    ii = mins[i].first; jj = mins[i].second;
        Cluster *iiC = exists(clusters, ii), *jjC = exists(clusters, jj);
        if(iiC && !jjC)
        {
            clusters.push_back(new Cluster(iiC, jj, min));
        }
        else
            if(jjC && !iiC)
            {
                clusters.push_back(new Cluster(jjC, ii, min));
            }
            else
                if(!iiC && !jjC)
                {
                    clusters.push_back(new Cluster(ii, jj, min));
                }
                else // exists(ii) && exists(jj)
                {
                    clusters.push_back(new Cluster(iiC, jjC, min));
                }
        sm[ii][jj] = 10000;

        //}

    }

    std::cout << clusters.size() << std::endl;
    std::vector<Cluster*>::iterator it;
    for(it = clusters.begin(); it != clusters.end(); it++)
    {
        std::cout << **it; // << std::endl;
    }
*/
    return 0;
}