Not an official ACM page
[ Problem F | 1998 ACM Finals problem set | My ACM problem archive | my home page]
The 1998 22nd Annual acm International Collegiate
Programming Contest World Finals
sponsored by IBM


Problem E
Petri Net Simulation


A Petri net is a computational model used to illustrate concurrent activity. Each Petri net contains some number of places (represented by circles), transitions (represented by black rectangles), and directed edges used to connect places to transitions, and transitions to places. Each place can hold zero or more tokens (represented by black dots). Here are two examples:

Example 1

Example 2

In the first Petri net above, there are two places (P1 and P2) and two transitions (T1 and T2). P1 initially has one token; P2 has none. P1 is an input place for transition T1, and P2 is an output place for T1. In the second example there are three places and three transitions, with three tokens in P1. T 2 has two input places, both of which are P2.

Operation of a Petri Net

Each transition in a Petri net is either enabled or disabled. A transition is enabled if there is at least one token in each of its input places. Any transition can fire whenever it is enabled. If multiple transitions are enabled, any one of them may fire. When a transition fires, one token is removed from each of the input places, and one token is added to each of the output places; this is effectively done atomically, as one action . When there are no enabled transitions, a Petri net is said to be dead.

In the top example only T1 is enabled. When it fires one token is remove d from P1, and one token is added to P2. Then T2 is enabled. When it fires one token is removed from P2, and one token is added to P1. Clearly this Petri net will repeat this cycle forever.

The bottom example is more interesting. T1 is enabled and fires, effectively moving a token to P2. At this point T1 is still the only enabled transition (T2 requires that P2 have two tokens before it is enabled). T1 fires again, leaving one token in P1 and two tokens in P2. Now both T1 and T2 are enabled. Assume T2 fires, removing two tokens from P2 and adding one token to P3. Now T1 and T3 are enabled. Continuing until no more transitions are enabled, you should see that only one token will be left in P2 after 9 transition firings. (Note that if T1 had fired instead of T2 when both were enabled, this result would have been the same after 9 firings.)

In this problem you will be presented with descriptions of one or more Petri nets. For each you are to simulate some specified number of transition firings, NF, and then report the number of tokens remaining in the places. If the net becomes dead before NF transition firings, you are to report that fact as well.

Input

Each Petri net description will first contain an integer NP (0 < NP < 100) followed by NP integers specifying the number of tokens initially in each of the places numbered 1, 2, ..., NP.Next there will appear an integer NT (0 < NT < 100) specifying the number of transitions. Then, for each transition (in increasing numerical order 1, 2, ..., NT) there will appear a list of integers terminated by zero. The negative numbers in the list will represent the input places, so the number -n indicates there is an input place at n. The positive numbers in the list will indicate the output places, so the number p indicates an output place at p. There will be at least one input place and at least one output place for each transition. Finally, after the description of all NT transitions, there will appear an integer indicating the maximum number of firings you are to simulate, NF. The input will contain one or more Petri net descriptions followed by a zero.

Output

For each Petri net description in the input display three lines of output. On the first line indicate the number of the input case (numbered sequentially starting with 1) and whether or not NF transitions were able to fire. If so, indicate the net is still live after NF firings. Otherwise indicate the net is dead, and the number of firings which were completed. In either case, on the second line give the identities of the places which contain one or more tokens after the simulation, and the number of tokens each such place contains. This list should be in ascending order. The third line of output for each set should be blank.

The input data will be selected to guarantee the uniqueness of the correct output displays.

Sample Input

2
 1 0
2
 -1 2 0
 -2 1 0
100
3
 3 0 
0
3
 -1 2 0
 -2 -2 3 0
 -3 1 0
100
0

Output for the Sample Input

Case 1: still live after 100 transitions
Places with tokens: 1 (1)

Case 2: dead after 9 transitions
Places with tokens: 2 (1)
This page maintained by Ed Karrels.
Last updated September 8, 1999