import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Optional {
    public int n,k;
    List<Character> alphabet=new ArrayList<Character>();
    int[] conexe;
    public static void main(String[] args)
    {
        long startTime = System.nanoTime();
        Optional work=new Optional();
        int check=work.getArguments(args);
        if(check == 0) {
            System.out.print("Input invalid!");
            return;
        }
        ArrayList<String> wordsArray=work.getWordsArray();
        work.displayWordsArray(wordsArray);
        boolean[][] adjacentMatrix=work.getAdjacentMatrix(wordsArray);
        work.displayAdjacentMatrix(adjacentMatrix);
        work.displayMostAndLeastN(wordsArray,adjacentMatrix);
        /*adjacentMatrix= new boolean[][]{
                {false, true, true, false, false, false},
                {true, false, true, false, false, false},
                {true, true, false, false, false, false},
                {false, false, false, false, true, false},
                {false, false, false, false, false, false},
                {false, false, false, false, false, false}
        };*/ //<- PENTRU TEST BONUS
        work.displayComponents(adjacentMatrix);
        long endTime   = System.nanoTime();
        long totalTime = endTime - startTime;
        System.out.print("execution time: ");
        System.out.println(totalTime);
    }
    public int getArguments(String[] values)
    {
        if(values.length <3)
            return 0;
        try {
            n = Integer.parseInt(values[0]);
            k = Integer.parseInt(values[1]);
            for(int i=2;i<values.length;i++)
            {
                if(values[i].length()!=1)
                    return 0;
                alphabet.add(values[i].charAt(0));
            }
        }
        catch(Exception e){
         return 0;
        }
        return 1;
    }
    public ArrayList<String> getWordsArray()
    {
        ArrayList<String> wordsArray=new ArrayList<String>();
        for(int i=0;i<n;i++) {
            StringBuilder row = new StringBuilder();
            for (int j = 0; j < k; j++) {
                int position = (int) (Math.random() * 1_000_000) % alphabet.size();
                char character = alphabet.get(position);
                row.append(character);
            }
            wordsArray.add(row.toString());
        }
        return wordsArray;
    }
    public void displayWordsArray(ArrayList<String> wordsArray)
    {
        for (String s : wordsArray)
            System.out.print(s+" ");
        System.out.println();
    }
    public boolean[][] getAdjacentMatrix(ArrayList<String> wordsArray)
    {
        boolean[][] adjacentMatrix=new boolean[n][n];
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
            {
                adjacentMatrix[i][j]=false;
                if(i==j)
                    continue;
                Word word1= new Word(wordsArray.get(i));
                Word word2= new Word(wordsArray.get(j));
                if(word1.isAdjacentWith(word2) == 1)
                    adjacentMatrix[i][j]=true;
            }
        return adjacentMatrix;

    }
    public void displayAdjacentMatrix( boolean[][] adjacentMatrix)
    {
        for(boolean[] row: adjacentMatrix)
        {
            for (boolean elem : row)
                System.out.print(elem + " ");
            System.out.println();
        }
    }
    public void displayMostAndLeastN(ArrayList<String> wordsArray,  boolean[][] adjacentMatrix)
    {
        int mostIndex=0,leastIndex=0,maxi=0,mini=n;
        int[] nrOfN =new int[n];
        Arrays.fill(nrOfN,0);
        for(int i=0; i<n; i++)
        {
            int currentN=0;
            for(int j=0; j<n; j++)
                if(adjacentMatrix[i][j])
                    currentN++;
            if(currentN<=mini)
            {
                mini=currentN;
                leastIndex=i;
            }
            if(currentN>maxi)
            {
                maxi=currentN;
                mostIndex=i;
            }
            nrOfN[i]=currentN;
        }
        System.out.print("Word with most neighbours: ");
        System.out.println(wordsArray.get(mostIndex));
        System.out.print("Word with least neighbours: ");
        System.out.println(wordsArray.get(leastIndex));
        boolean sameNrOfN=true;
        for(int i=0;i<n;i++)
        {
            if(nrOfN[i]!=nrOfN[leastIndex])
            {
                System.out.println("Not all words have the same nr of neighbours");
                sameNrOfN=false;
                break;
            }
        }
        if(sameNrOfN)
            System.out.println("All words have the same nr of neighbours");
    }
    public void addComp( int node,boolean[][] adjacentMatrix, int comp)
    {
        if(conexe[node] == 0)
        {
            System.out.println(node+" "+comp);
            conexe[node]=comp;
            for(int i=0; i<adjacentMatrix[0].length ; i++)
                if(adjacentMatrix[node][i] && conexe[i]==0)
                    addComp(i,adjacentMatrix,comp);
        }
    }
    public void displayComponents(boolean[][] adjacentMatrix)
    {
        conexe=new int[n];
        Arrays.fill(conexe,0);
        int comp=0;
        for(int i=0; i<n; i++)
            if(conexe[i]==0)
            {
                comp++;
                addComp(i,adjacentMatrix,comp);
            }
        for(int i=1;i<=comp; i++)
        {   System.out.println("Componenta "+i);
            for(int j=0; j < n; j++)
                if(conexe[j]==i)
                    System.out.print(j+" ");
            System.out.println();
        }
    }



}