问题描述 一个Petri网是一个计算模型,用来说明并发事件。每个Petri网包含一些库所(被表示成圆圈),变迁(被表示成黑色的矩形),和一些有向边,用来连接库所到变迁,和变迁到库所。每个库所能够包含0个或多个令牌(被表示)。 这里有2个例子: 在上面的第一个Petri网中,有2个库所(P1 和 P2)和2个变迁(T1 和 T2)。P1初始有1个令牌。P2没有令牌。P1是变迁T1的输入库所,P2是T1的输出库所。在第二个例子中,有3个库所和3个变迁,P1有3个令牌。T2有2个输入库所,2个都是P2。 一个Petri网的操作 每个Petri网的变迁要么被允许,要么不被允许。一个变迁被允许当且仅当每个输入库所都至少有1个令牌。任何被允许的变迁可以发生。如果有多个变迁被允许,任何一个都可能发生。当一个变迁发生时,每个输入库所都会移除1个令牌,每个输出库所都会增加1个令牌。这会有效地利用原子能来完成,作为一个事件。如果没有一个变迁被允许,这个Petri网就被认为是死的。 最上面那个例子,只有T1是被允许的。当它发生时,会从P1移除1个令牌,给P2增加1个令牌。然后T2就被允许了。当它发生时,会从P2移除1个令牌,给P1增加1个令牌。显然,这个Petri网将会永远重复这个循环。 下面那个例子更加有趣。T1被允许然后发生,有效地移动1个令牌给P2。在这个时候,T1仍然是唯一被允许的变迁(T2被允许需要P2有2个令牌)。T1再次发生,在P1剩下1个令牌,P2中有2个令牌。现在,T1和T2都被允许。假设T2发生,从P2移除2个令牌,给P3增加1个令牌。现在T1和T3都被允许。直到没有变迁被允许,你应该能看到在9次变迁发生后,在P2仅留下1个令牌。(注意到,如果当T1和T2都被允许的时候,T1代替了T2发生,这个结果也同样是在9次变迁发生后。) 在这个问题中,你将会被给出1个或多个Petri网的描述。对于每个描述,你将要模拟NF(0 < NF < 1000)次变迁的发生,然后输出留在库所里的令牌数量。如果这个Petri网在NF次变迁发生之前就死了,你将按事实输出。 输入格式 每个Petri网的描述首先会包含一个整数NP(0 < NP < 100),紧接着有NP个整数分别表示编号为1,2,...,NP的库所初始有多个个令牌。接着会有一个整数NT(0 < NT < 100)表示变迁的数量。然后,对于每个变迁(编号为1,2,...,NT)将会有一个以0结尾的整数序列。序列中的负数代表输入库所,所以数字-n代表有一个输入库所在n。序列中的正数代表输出库所,所以数字p代表有一个输出库所在p。每个库所至少有一个输入库所,至少有一个输出库所。最后,在NT个变迁的描述之后,会有一个整数代表你至多要模拟变迁发生的次数,NF。输入会包含一个或多个Petri网的描述,最后会有一个0。 输出格式 对于每个Petri网的描述,输出三行。第一行输出是第几组数据(从1开始连续编号)和是否有NF次变迁发生。如果有,输出这个Petri网在NF次变迁发生后仍然活着。否则输出这个Petri网已经死了和变迁发生的次数。两种情况下,在第二行都输出在模拟结束后,包含1个或多个令牌的库所的编号,和每个这种库所含有的令牌数量。输出的序列按编号递增。每组数据的第三行都应该是空行。 输入数据将会被选择来保证正确输出的唯一性。 样例输入 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 样例输出 Case 1: still live after 100 transitions Places with tokens: 1 (1) Case 2: dead after 9 transitions Places with tokens: 2 (1) 数据规模和约定 0 < NP < 100; 0 < NT < 100; 0 < NF < 1000; 每个库所初始的令牌数不超过10000。 每个Petri网的所有变迁输入的整数序列的总长度不超过20000。 每个测试点包含不超过5个Petri网的描述。