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

public class DFA
{
    private boolean cyclesInPath;
    private int currentState;
    private int maxCount;
    private boolean stopAddingStrings;
    private ArrayList<Integer> acceptedStates = new ArrayList<>();
    private ArrayList<Transition> transitions = new ArrayList<>();
    private ArrayList<String> acceptedStrings = new ArrayList<>();

    private int tempFrom;
    private int tempTo;
    private int tempC;

    public DFA(int stateCount, int startState)
    {
        cyclesInPath = false;
        currentState = startState;
        tempFrom = -1;
        tempTo = -1;
        tempC = '-';
        stopAddingStrings = false;
    }

    public void setAccepting(int state)
    {
        acceptedStates.add(state);
    }

    public void addTransition(int from, int to, char c)
    {
        if(tempFrom == -1 && tempTo == -1 && tempC == '-')
        {
            transitions.add(new Transition(from, to));
            transitions.get(transitions.size() - 1).addC(c);
            tempFrom = from;
            tempTo = to;
            tempC = c;
        }
        else if(from == tempFrom && to == tempTo)
            transitions.get(transitions.size() - 1).addC(c);
        else
        {
            transitions.add(new Transition(from, to));
            transitions.get(transitions.size() - 1).addC(c);
            tempFrom = from;
            tempTo = to;
            tempC = c;
        }
    }

    public List<String> getAcceptingStrings(int maxCount)
    {
        this.maxCount = maxCount;
        work(currentState, 0, "");
        return acceptedStrings;
    }

    private void work(int currentState, int cycle, String path)
    {
        if(acceptedStrings.size() >= maxCount)
            return;

        for(int a = 0; a < acceptedStates.size(); a++)
        {
            if(currentState == acceptedStates.get(a) && path != "")
            {
                stopAddingStrings = false;
                addValidStrings(path, "");
                for(int b = 0; b < transitions.size(); b++)
                {
                    transitions.get(b).visited = 0;
                }
                break;
            }
        }

        for(int a = 0; a < transitions.size() && acceptedStrings.size() < maxCount; a++)
        {
            if(a > 0 && !cyclesInPath) break;
            for(int b = 0; b < transitions.size() && acceptedStrings.size() < maxCount; b++)
            {
                Transition transition = transitions.get(b);
                if(currentState == transition.from)
                {
                    if(cycle < transition.visited)
                    {
                        cyclesInPath = true;
                        return;
                    }
                    transition.visited++;
                    work(transition.to, a, path + b);
                }
                /*if(b == transitions.size() - 1)
                {
                    return;
                }*/
            }
        }
    }

    //Adds all valid strings for the current path.
    private void addValidStrings(String path, String word)
    {
        int index = path.charAt(0) - '0';
        path = path.substring(1);
        for(int a = 0; a < transitions.get(index).chars.size(); a++)
        {
            String tempword = word;
            for(int b = 0; b <= a; b++)
            {
                tempword += transitions.get(index).chars.get(b);
            }
            if(path.compareTo("") != 0)
            {
                addValidStrings(path,tempword);
                if(stopAddingStrings) return;
            }
            else
            {
                if(acceptedStrings.size() >= maxCount)
                {
                    stopAddingStrings = true;
                    return;
                }
                acceptedStrings.add(tempword);
            }
        }
    }

    private boolean duplicate(String s)
    {
        for(int a = 0; a < acceptedStrings.size(); a++)
        {
            if(acceptedStrings.get(a).compareTo(s) == 0)
            {
                return true;
            }
        }
        return false;
    }
}

class Transition
{
    ArrayList<Character> chars;
    int from;
    int to;
    int visited;

    Transition(int from, int to)
    {
        chars = new ArrayList<>();
        this.from = from;
        this.to = to;
        visited = 0;
    }

    public void addC(char c)
    {
        chars.add(c);
    }
}