1592. Synchronous Design

输入格式

The input file contains several circuits. The first line gives the number of circuits in the file.

For each circuit in the file, the first line contains the clock period for the circuit, given as an integer number in nanoseconds. The next line gives the number of nodes. The following lines each contain a node, described by a letter and a integer number. The letter is ‘i’ for an input, ‘o’ for an output, ‘a’ for an asynchronous node and ‘s’ for a synchronous node. The number gives the delay introduced by the node as an integer number in nanoseconds (only meaningful for an asynchronous node). Nodes are implicitly numbered, starting at zero.

After the nodes, the number of connections for the circuit follows. Each following line contains a pair of integer numbers denoting a connection between the output and the input of two nodes. The connection links an output of the node given by the first number and an input of the node given by the second number.

The clock signal is not given in the input file. We assume that all synchronous nodes are properly connected to the clock signal.

输出格式

For each circuit in the input file, your output file should contain a line with one of the following messages:

“Synchronous design. Maximum delay: .” if the circuit has a synchronous design.

should be replaced by the longest delay found on any path between two synchronous nodes.

“Circuit contains cycle.” if the circuit contains a cycle composed exclusively of asynchronous nodes.

“Clock period exceeded.” if there is a path between two synchronous nodes that is longer than the given clock period and there are no cycles composed of asynchronous nodes.

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

Synchronous design. Maximum delay: 28.