C++

You are planning a vacation around Europe (and some other places because you had a hard time deciding) and wish to determine the number of possible itineraries before booking the trip. However, there are a lot of constraints due to flights, money, picky friends, and hotels. You will receive a directed acyclic graph of the cities you wish to visit, and must produce all possible orders to visit them in alphabetically.

Input Format

The first line will consist of a single integer, n, indicating the number of nodes in the graph. The next n lines will each consist of a string (the data in that node), followed by a colon, followed by a comma-separated list of strings that indicate the data in the nodes adjacent to the first node. For example,

10 nyc: london, istanbul, paris, la la: london, lisbon, honolulu honolulu: lisbon, istanbul lisbon: porto, barcelona paris: barcelona, honolulu, la madrid: porto istanbul: porto: london: barcelona, lisbon, madrid barcelona: istanbul, madrid 

Therefore, london, istanbul, paris, and la are adjacent to nyc; london, lisbon, and honolulu are adjacent to la; lisbon and istanbul are adjacent to honolulu; and so on.

Constraints

You can assume the input is valid (i.e., that it represents a directed acyclic graph).

Output Format

Comma-separated lines representing all possible topological sorts of the input, in alphabetical order. For example, for the above input:

nyc, paris, la, honolulu, london, lisbon, barcelona, istanbul, mardrid, porto nyc, paris, la, honolulu, london, lisbon, barcelona, mardrid, istanbul, porto nyc, paris, la, honolulu, london, lisbon, barcelona, mardrid, porto, istanbul nyc, paris, la, london, honolulu, lisbon, barcelona, istanbul, mardrid, porto nyc, paris, la, london, honolulu, lisbon, barcelona, mardrid, istanbul, porto nyc, paris, la, london, honolulu, lisbon, barcelona, mardrid, porto, istanbul 

Sample Input 0

10 nyc: london, istanbul, paris, la la: london, lisbon, honolulu honolulu: lisbon, istanbul lisbon: porto, barcelona paris: barcelona, honolulu, la madrid: porto istanbul: porto: london: barcelona, lisbon, madrid barcelona: istanbul, madrid 

Sample Output 0

nyc, paris, la, honolulu, london, lisbon, barcelona, istanbul, madrid, porto nyc, paris, la, honolulu, london, lisbon, barcelona, madrid, istanbul, porto nyc, paris, la, honolulu, london, lisbon, barcelona, madrid, porto, istanbul nyc, paris, la, london, honolulu, lisbon, barcelona, istanbul, madrid, porto nyc, paris, la, london, honolulu, lisbon, barcelona, madrid, istanbul, porto nyc, paris, la, london, honolulu, lisbon, barcelona, madrid, porto, istanbul