Network Wars

It is the year 2126 and, as predicted, comet Swift-Tuttle has struck the earth. The resulting explosion emits a huge cloud of high-energy neutrons that wipes out all human life. The accompanying electromagnetic storm causes two unusual events: many of the links between different parts of the electronic network are severed, and some postgraduate AI projects begin to merge and mutate, much as animal life did several million years ago. Within a very short time two programs emerge, Paskill and Lisper, which move through the network marking every node they visit. Paskill activates a modified Prolog interpreter and Lisper activates the "Hello World" program. However, "Hello World" has mutated into an endless loop that so ties up a node that no other program — not even Lisper — can re-enter it, while the Prolog interpreter immediately reverse-compiles (and destroys) any program that enters its node. Paskill, however, remembers every node it has visited and never tries to re-enter one. Thus, if Lisper tries to enter a node already visited by Paskill it is annihilated; neither program can enter a node already visited by Lisper; if either (or both) cannot move, both halt; and if they ever arrive at a node simultaneously they annihilate each other. Both programs move at the same speed.

Write a program to simulate these events. Every node in the network is labelled with a single uppercase letter, as shown below. When moving to the next node, Paskill searches alphabetically forwards from the current node, whereas Lisper searches alphabetically backwards, both wrapping around if necessary. Thus (in the absence of the other) if Paskill enters the network below at A it visits the nodes in the order A, B, C, D, G, H, E, F; if Lisper enters at H it visits them in the order H, G, E, F. The simulation stops when one or more of the above events occurs. If more than one event occurs, mention Paskill first.

The input consists of a series of lines. Each line describes one network and gives the starting nodes for the two programs. A network is described as a series of nodes separated by ';' and terminated by a period ('.'). Each node is described by its identifier, a ':', and one or more of the nodes connected to it. Every link is mentioned at least once, as is every node, although not every node is separately 'described'. After the period come the labels of the starting nodes — first Paskill, then Lisper. No line contains more than 255 characters. The input is terminated by a line consisting of a single '#'.

The output consists of one line for each network. Each line states the terminating event and the node where it occurs. The terminating event is one or two of the following:

• Lisper destroyed in node ?
• {Paskill/Lisper} trapped in node ?
• Both annihilated in node ?