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

public class DFA
{
    private int currentState;
    private int maxCount;
    private final int stateCount;
    private final int startState;
    private ArrayList<Integer> acceptedStates = new ArrayList<>();
    private ArrayList<Transition> transitions = new ArrayList<>();
    private ArrayList<String> acceptedStrings = new ArrayList<>();

    public DFA(int stateCount, int startState)
    {
        this.stateCount = stateCount;
        this.startState = startState;
        currentState = startState;
    }

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

    public void addTransition(int from, int to, char c)
    {
        transitions.add(new Transition(from,to,c));
    }

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

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

        for(int a = 0; a < acceptedStates.size(); a++)
        {
            if(currentState == acceptedStates.get(a) && word != "" && !duplicate(word))
            {
                acceptedStrings.add(word);
                break;
            }
        }

        for(int a = 0; a < transitions.size() && acceptedStrings.size() < maxCount; a++)
        {
            Transition transition = transitions.get(a);

            if(currentState == transition.from)
            {
                if(transition.from == transition.to && !cycle) continue;

                word += transition.c;
                transition.visited = true;
                work(transition.to, transition.from, word, false);
                work(transition.to, transition.from, word, true);
                transition.visited = false;
            }
        }
    }

    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
{
    int from;
    int to;
    char c;
    boolean visited;

    Transition(int from, int to, char c)
    {
        this.from = from;
        this.to = to;
        this.c = c;
        visited = false;
    }
}