本题没有可用的提交语言。

题目描述

在实际应用中，软件系统可能非常复杂，特别是当它们采用分布式、网络化、多线程或并发技术实现时。调试这些系统十分困难，因为系统可能进入众多可能的状态之一。想象在任意时刻，你对程序的内存（或变量值）进行一次快照，这就是程序的一个状态。通常，程序通过执行语句从一个状态转移到另一个状态。

假设我们需要检查程序是否能正确运行。首先，我们将程序抽象为一个有限状态机（FSM）。如图1所示，状态用圆圈表示，起始状态由一条无符号且无源状态的边指向。边上的符号$a, b, c, d$表示触发状态转移的动作。

理论上，程序包含以下行为模式：
abdabdabdabd.....
abdcdabdcdabdcd....
cdbdcdbdcdbd......
abdcdbd.........
..................

每个无限序列都是FSM的一个可能运行路径，这些无限序列的集合称为程序的行为。有时，我们需要检查程序是否在任何可能的行为中出现错误。例如，假设动作$a$是请求内存，$b$是释放内存。我们可能希望确保在任何运行中，$a$总是出现在$b$之前，且$b$不会在没有$a$的情况下出现。我们可以用另一个FSM（如图2）描述这一需求。黑色状态表示陷阱状态（编号为$-1$），一旦运行进入该状态，就无法离开。当运行进入陷阱状态时，需求被违反。

给定一个FSM（程序）和一个需求（也用FSM描述），你的目标是编写程序，判断该需求是否被程序的所有可能行为满足，或者是否至少存在一个运行路径会违反需求。例如，图1中的FSM存在运行路径$abdcdb.....$，其中第二个$b$在没有$a$先出现的情况下发生，因此违反了需求。

输入格式

测试文件以数字$n$（$n \leq 10$，测试用例数量）开头。每个测试用例包含两个FSM：第一个是程序，第二个是需求。

每个FSM的第一行为三个数字$s\ e\ i$，其中：
• $s$是状态数量（$2 \leq s \leq 500$）；
• $e$是边数量（$2 \leq e \leq 2000$）；
• $i$是起始状态。

接下来是$e$行边描述，每行包含起始状态、动作符号（$a$–$z$）和目标状态。陷阱状态用$-1$表示。两个FSM的数据之间用空行分隔。

输出格式

对于每个测试用例：
• 如果没有运行路径违反需求，输出"satisfied"；
• 如果至少存在一个运行路径会进入陷阱状态，输出"violated"。

输入数据 1

2  
4 5 1  
1 a 2  
2 b 3  
1 c 4  
4 d 2  
3 d 1  

3 4 1  
1 a 2  
2 b 1  
1 b -1  
2 a -1  

4 5 1  
1 a 2  
2 b 3  
1 c 4  
4 a 2  
3 d 1  

3 4 1  
1 a 2  
2 b 1  
1 b -1  
2 a -1  

输出数据 1

violated  
satisfied  

提示

你需要找到一种方法将两个FSM"合并"，即构造一个新的FSM，其行为是两个FSM行为的组合。然后检查该组合行为中是否存在陷阱状态。

来源

台湾 2004