Synchronous Design

Designers of digital integrated circuits (ICs) care deeply about the correctness of their designs, because unlike software, an IC cannot be tested easily. Real testing is only possible after the design has been finalized and the chip has been manufactured.

To simulate the behavior of a digital IC and to give reasonable confidence that the finished chip will work, essentially every digital IC today uses a synchronous design.

In a synchronous design, an external clock signal drives the IC from one well-defined, stable state to the next. On the active edge of the clock, every input, output, and internal node is stable in either the high or the low state. Between two consecutive clock edges, the signals and nodes may change and may pass through any intermediate state. The behavior of a synchronous network is predictable and does not fail because of hazards or glitches caused by imperfections of the real circuit.

To decide whether an IC is a valid synchronous design, we distinguish synchronous nodes from asynchronous nodes.

• Flip-flops are synchronous nodes. On the active edge of the clock, a flip-flop's output takes the state of its input and holds that state for the entire next clock cycle. Synchronous nodes are connected to the clock signal.
• Simple gates such as AND or OR are asynchronous nodes. Their output changes, after a short delay, whenever any of their inputs changes, and during that transition the output may briefly enter an undefined, intermediate state.

For simplicity, assume that every input of the circuit is driven directly by the output of a synchronous node outside the circuit, and that every output of the circuit directly drives the input of a synchronous node outside the circuit.

An IC is a valid synchronous design when both of the following conditions hold:

1. Clock period. The signal delay along every path between two synchronous nodes must be less than or equal to the clock period, so that all nodes have enough time to settle. For example, a path whose accumulated delay is 43ns violates a clock period of 30ns.
2. No asynchronous cycles. There must be no cycle made up exclusively of asynchronous nodes. In a real circuit, such a cycle could oscillate.

You may safely assume that:

• the delay between any input and any output of the same node is the same, i.e. equal to the delay given for that node;
• synchronous nodes have no delay at all;
• every connection links the output of one node to the input of another node.

Write a program that, given a network of synchronous and asynchronous nodes together with a delay for each node, a set of inputs and outputs, and the clock period, decides whether the circuit is a valid synchronous design.

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

For each circuit:

• The first line contains the clock period, an integer number of nanoseconds.
• The second line contains the number of nodes.
• Each of the following lines describes one node with a letter and an integer. The letter is i for an input, o for an output, a for an asynchronous node, and s for a synchronous node. The integer is the delay introduced by the node in nanoseconds (meaningful only for asynchronous nodes). Nodes are numbered implicitly, starting at 0.
• The next line contains the number of connections.
• Each of the following lines contains two integers u v, a connection from an output of node u to an input of node v.

The clock signal itself is not part of the input; assume that all synchronous nodes are properly connected to it.

For each circuit, print one line containing one of the following messages:

• Synchronous design. Maximum delay: <ss>. if the circuit is a valid synchronous design, where <ss> is replaced by the largest delay found on any path between two synchronous nodes.
• Circuit contains cycle. if the circuit contains a cycle made up exclusively of asynchronous nodes.
• Clock period exceeded. if there is no cycle of asynchronous nodes but there is a path between two synchronous nodes that is longer than the clock period.

When more than one condition could apply, an asynchronous cycle is reported first.