import java.io.IOException;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;

class link {
    int a; //Куда направлено ребро
    int mom; //Откуда
    int ves;
    link(int tsel, int parent, int vesSvyazi) {
        a = tsel;
        mom = parent;
        ves = vesSvyazi;
    }
}

class Comp implements Comparator<link> {
    @Override
    public int compare(link t, link t1) {
        Integer a = t.ves;
        Integer b = t1.ves;
        return a.compareTo(b);
    }
}

public class Kruskal {
    static ArrayList<link>[] graf;
    static HashSet<HashSet<Integer>> mnozh;
    final static int numLinks = 17;
    final static int numVersh = 10;

    static void init() {
        graf[0].add(new link(1, 0, 8));
        graf[0].add(new link(2, 0, 6));
        graf[0].add(new link(3, 0, 10));

        graf[1].add(new link(4, 1, 1));

        graf[2].add(new link(5, 2, 8));
        graf[2].add(new link(6, 2, 6));

        graf[3].add(new link(6, 3, 1));

        graf[4].add(new link(9, 4, 2));

        graf[5].add(new link(1, 5, 5));

        graf[6].add(new link(8, 6, 1));

        graf[7].add(new link(3, 7, 7));
        graf[7].add(new link(9, 7, 3));

        graf[8].add(new link(7, 8, 4));
        graf[8].add(new link(9, 8, 8));
        graf[8].add(new link(3, 8, 1));
        graf[8].add(new link(5, 8, 4));

        graf[9].add(new link(5, 9, 2));
    }

    public static void main(String[] args) throws IOException {
        Queue<link> q = new PriorityQueue(numLinks, new Comp());
        ArrayList<link> minOstGraf = new ArrayList();
        graf = new ArrayList[numVersh];
        mnozh = new HashSet<>();
        for (int i = 0; i < numVersh; i++) {
            graf[i] = new ArrayList<>();
            HashSet<Integer> vr = new HashSet();
            vr.add(i);
            mnozh.add(vr);
        }
        init();

        //Заполняем очередь
        for (int i = 0; i < numVersh; i++) {
            Iterator<link> itr = graf[i].iterator();
            while (itr.hasNext()) {
                q.offer(itr.next());
            }
        }
        for (; q.size() > 0;) {
            link lka = q.poll();
            System.out.println(lka.mom + " " + lka.a);

            //Проход по множеству
            Iterator<HashSet<Integer>> itr1 = mnozh.iterator();
            label1:
            for (; itr1.hasNext();) {
                HashSet<Integer> mom = itr1.next(); //Запоминаем множество 1
                if (mom.contains(lka.mom) && !mom.contains(lka.a)) {
                    //Проход по множеству во множестве
                    Iterator<HashSet<Integer>> itr2 = mnozh.iterator();
                    while (itr2.hasNext()) {
                        HashSet<Integer> son = itr2.next(); //Запоминаем множество 2
                        if (son.contains(lka.a)) {
                            mom.addAll(son); //Слияние множеств 1 и 2
                            minOstGraf.add(lka);
                            System.out.println(son + " поглощается..");
                            son.clear();
                            break label1;
                        }
                    }
                }
            }

            //Вывод множеств для наглядности
            Iterator<HashSet<Integer>> itr = mnozh.iterator();
            for (int i = 0; itr.hasNext(); i++) {
                System.out.print(itr.next() + " ");
            }
            System.out.println();
        }
        System.out.println("Связи готового дерева:");
        for (int i = 0; i < minOstGraf.size(); i++) {
            char a = 'a', b = 'a';
            a += minOstGraf.get(i).mom;
            b += minOstGraf.get(i).a;
            System.out.println(a + "" + b + " Вес: " + minOstGraf.get(i).ves);
        }
    }
}