Theseus and the Minotaur

Those of you with a classical education may remember the legend of Theseus and the Minotaur — an unlikely tale of a bull-headed monster, an underground maze full of twisty little passages all alike, love-lorn damsels, and balls of silk. In keeping with the educational nature of this contest, we now reveal the true story.

The maze was actually a series of caverns connected by reasonably straight passages, some of which could be traversed in only one direction. To trap the Minotaur, Theseus — having discovered that the Minotaur was afraid of light — smuggled a large supply of candles into the Labyrinth. Theseus wandered aimlessly until he heard the Minotaur approaching along a tunnel. At that point he lit a candle and set off in pursuit. The Minotaur retreated into the cavern it had just left and fled by another passage. Theseus followed, slowly gaining, until he reached the $k$-th cavern since lighting the candle. There he had just enough time to place the lit candle in the middle of the cavern, light another from it, and continue the chase. As the chase progressed, a candle was left in every $k$-th cavern passed through (counting the cavern where the chase began as the first), gradually limiting the Minotaur's movement.

Whenever the Minotaur entered a cavern, it checked that cavern's exits in a fixed order and fled down the first exit that did not lead directly to a lit cavern. Because Theseus was right behind, carrying a lit candle, the Minotaur never left a cavern by the tunnel it had just used to enter. Eventually the Minotaur became trapped, letting Theseus defeat it.

Consider the following Labyrinth as an example, in which the Minotaur checks the exits of each cavern in alphabetical order:

Suppose Theseus is in cavern C when he hears the Minotaur approaching from A, and that $k = 3$. He lights a candle and gives chase, pursuing the Minotaur through A, B, D (leaves a candle), G, E, F (another candle), H, E, G (another candle), H, E (where it is finally trapped).

Write a program that simulates Theseus's pursuit. A labyrinth description identifies each cavern by an uppercase letter and lists, for each cavern, the caverns reachable from it in the order the Minotaur will try them. This is followed by the identifiers of the caverns the Minotaur and Theseus were in when contact was first made, and then the value of $k$.

The input consists of a series of lines, each describing one scenario in the format shown below. No line contains more than 255 characters. The input is terminated by a line containing a single #.

Each scenario line has the form:

maze. M T k

• maze is a list of cavern:neighbours entries separated by semicolons (;) and terminated by a period (.). Each entry gives a cavern's uppercase identifier, a colon, and the identifiers of the caverns reachable from it, listed in the order the Minotaur will attempt them. For example, A:BCD means that from cavern A the Minotaur tries B first, then C, then D.
• M is the identifier of the cavern the Minotaur was in, and T the identifier of the cavern Theseus was in, when contact was first made.
• k is a positive integer: a candle is left in every $k$-th cavern the chase passes through.

For each labyrinth, print one line describing the outcome of the chase. First print the identifiers of the caverns where candles were left, in the order the candles were placed, each followed by a single space. Then print a slash (/) immediately followed by the identifier of the cavern in which the Minotaur was finally trapped.