/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package sccfind;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

public class Main {

    final static int UNDEFINED = -1;
    static int index = 0;

    static Stack<String> zasobnik = new Stack<String>();
    static Map<String, List<String>> vrcholy = new HashMap<String, List<String>>();
    static List<List<String>> komponenty = new ArrayList<List<String>>();
    static Map<String, Integer> indexy = new HashMap<String, Integer>();
    static Map<String, Integer> values = new HashMap<String, Integer>();


    public static void sccFind(String vrchol) {

        String tempVrchol;

        // nastaveni hloubky vrcholu v DFS strome
        indexy.put(vrchol, index);
        values.put(vrchol, index++);

        // vrcholy si zaznamenavame v zasobniku
        zasobnik.add(vrchol);

        /*
         *
         * Prozkoumame sousedy,
         * bud jsou jeste nenavstiveni => rekurzivne prohledame
         * nebo jsou jiz navstiveni
         *
         */
        for(String soused : vrcholy.get(vrchol)) {
            if(indexy.get(soused) == -1) {
                sccFind(soused);
                values.put(vrchol, Math.min(values.get(vrchol),values.get(soused)));
            } else if(zasobnik.contains(soused)) {
                values.put(vrchol,Math.min(values.get(vrchol),indexy.get(soused)));
            }
        }

        /*
         * 
         * Pokud uz jsme sousedy prohledali a jsme zpatky v koreni,
         * muzeme komponentu zapsat
         *
         */
        if(values.get(vrchol) == indexy.get(vrchol)) {
            List<String> komponenta = new ArrayList<String>();
            do {
                tempVrchol = zasobnik.pop();
                komponenta.add(tempVrchol);
            } while(!tempVrchol.equals(vrchol));
            
            komponenty.add(komponenta);
        }

    }

    public static void main(String[] args) throws FileNotFoundException, IOException {

        String inputFile = "/afs/ms/u/k/kolarij/data.txt";
        int aktual_id = 0;

        if(args.length > 0)
            inputFile = args[0];

        BufferedReader soubor = new BufferedReader(new FileReader(inputFile));

        String radek;
        String pom = "";
        String[] aktualSlova;

        // nacteni vrcholu ze vstupu do seznamu vrcholu + inicializace hodnot
        while((radek = soubor.readLine()) != null) {
            aktualSlova = radek.split(" ");
            List<String> sousedi = new ArrayList<String>();
            for(int k = 1; k < aktualSlova.length; k++) {
                sousedi.add(aktualSlova[k]);
            }
            pom = aktualSlova[0].substring(0, aktualSlova[0].length()-1);
            vrcholy.put(pom,sousedi);
            indexy.put(pom, -1);
            values.put(pom, -1);
        }

        // prohledavani do hloubky pro kazdy zatim neobjeveny vrchol
        for(String vrchol : vrcholy.keySet()) {
            if(indexy.get(vrchol) == UNDEFINED)
                sccFind(vrchol);
        }

        int pocet = 0;
        String pomVrchol;
        boolean exists;

        // vypis komponent
        for(List<String> komponenta : komponenty) {
            // osetreni jednoprvkovych komponent bez smycky
            exists = false;
            if(komponenta.size() == 1) {
                pomVrchol = komponenta.get(0);
                for(String soused : vrcholy.get(pomVrchol)) {
                    if(soused.equals(pomVrchol)) {
                        exists = true;
                        break;
                    }
                }
                if(!exists)
                    continue;
            }
            
            System.out.print("Komponenta cislo " + ++pocet + ": ");
            for(String vrchol : komponenta) {
                System.out.print(vrchol + " ");
            }
            System.out.println();
        }
    }

}