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

描述

数字集成电路（IC）的设计者非常关注他们设计的正确性，因为与软件不同，集成电路很难进行测试。在设计最终确定并且集成电路生产出来之前，不可能进行真正的测试。

为了模拟数字集成电路的行为，并且在一定程度上保证最终的芯片能够正常工作，如今所有的数字集成电路都基于同步设计。

图：关键路径（虚线）需要 43 纳秒才能稳定下来

在同步设计中，一个外部时钟信号触发集成电路从一个定义明确且稳定的状态转变到下一个状态。在时钟的有效沿上，所有的输入和输出信号以及所有的内部节点都稳定处于高电平或低电平状态。在时钟的两个连续沿之间，信号和节点被允许发生变化，并且可能处于任何中间状态。同步网络的行为是可预测的，并且不会因为实际电路的不规则性所引入的冒险或毛刺而失效。

为了分析一个集成电路是否具有同步设计，我们区分同步节点和异步节点。触发器是同步节点。在时钟的有效沿上，触发器的输出会变为输入的状态，并在接下来的时钟周期内保持该状态。同步节点与时钟信号相连。

像与门或或门这样的简单门电路是异步节点。只要它们的任何一个输入发生变化，它们的输出就会（在短时间延迟后）发生变化。在那个过渡阶段，输出甚至可能进入一些未定义的或中间的状态。

为了简化问题，我们假设电路的所有输入都直接连接到电路外部的一个同步节点的输出，并且电路的所有输出都直接连接到电路外部的一个同步节点的输入。

对于一个集成电路要具有同步设计，主要必须满足两个要求：

• 两个同步节点之间引入的信号延迟必须小于或等于时钟周期，这样节点才有足够的时间变得稳定。在图 1 中，圆角框表示异步节点，而方角框表示同步节点。虚线路径上引入的延迟是 43 纳秒，超过了给定的 30 纳秒的时钟周期。
• 不能存在完全由异步节点组成的循环。在实际电路中，这样的循环可能会产生振荡。在图 2 中，虚线路径构成了一个由异步节点组成的循环。

图 3 展示了一个具有同步设计的电路。它不包含由异步节点组成的循环，并且两个同步节点之间的最长路径比 30 纳秒的时钟周期要短。

图：该设计包含一个循环（虚线）

图：一个同步设计

你需要编写一个程序，来判断给定的一个集成电路是否具有同步设计。你会得到一个由同步节点和异步节点组成的网络、每个节点的延迟、一些输入和输出以及时钟周期。

你可以放心地假设：

• 同一节点的任何输入和任何输出之间引入的延迟是相等的，即等于为该节点给定的延迟。
• 同步节点根本没有延迟。
• 两个节点之间的所有连接都是将一个输出连接到一个输入。

输入

输入文件包含多个电路。第一行给出文件中电路的数量。

对于文件中的每个电路，第一行包含该电路的时钟周期，以纳秒为单位的整数给出。下一行给出节点的数量。接下来的每一行包含一个节点，由一个字母和一个整数描述。字母 'i' 表示输入，'o' 表示输出，'a' 表示异步节点，'s' 表示同步节点。该整数给出该节点引入的延迟，以纳秒为单位的整数（仅对异步节点有意义）。节点隐含地从 0 开始编号。

在节点信息之后，是该电路的连接数量。接下来的每一行包含一对整数，表示两个节点的输出和输入之间的连接。该连接将第一个数字所表示节点的输出与第二个数字所表示节点的输入相连。

时钟信号不在输入文件中给出。我们假设所有的同步节点都已正确连接到时钟信号。

输出

对于输入文件中的每个电路，你的输出文件应该包含一行，其中包含以下消息之一：

• “Synchronous design. Maximum delay: < ss >.”，如果该电路具有同步设计。
• < ss > 应该被替换为在任意两个同步节点之间的任何路径上找到的最长延迟。
• “Circuit contains cycle.”，如果该电路包含一个完全由异步节点组成的循环。
• “Clock period exceeded.”，如果存在两个同步节点之间的路径长度超过给定的时钟周期，并且不存在由异步节点组成的循环。

输入数据 1

1
30
10
i 0
i 0
i 0
i 0
o 0
o 0
a 9
a 11
a 8
s 0
9
0 8
1 7
2 6
2 6
6 7
7 8
8 4
7 9
9 5

输出数据 1

Synchronous design. Maximum delay: 28.

来源

1995 年西南欧洲区域竞赛