UML Syntax

UML (Unified Modeling Language) is a standardized modeling language used for developing complex object-oriented software projects. One of its components is the activity diagram, which describes the algorithms of interacting parallel processes.

In its simplest form, an activity diagram can be represented as a scheme consisting of nodes and arcs. Each node corresponds to an activity, while an arc represents the transfer of control between two nodes.

A scheme is considered correct if it consists of nodes of the following five types:

1. State: An action is performed in this node. It has at most one arc entering and at most one arc exiting.

2. Decision: This node has one arc entering and two or more arcs exiting. Each exiting arc corresponds to a condition, and only one of the conditions should be true. Control is transferred along the arc of the true condition.

3. Merge: This node has two or more arcs entering and one exiting. A merge signifies the end of several conditional behavior paths initiated by a decision.

4. Synchronization Bar: This node has one arc entering and at least two arcs exiting. It is used to describe the parallel behavior of the system. When executed, control is transferred along all exiting arcs.

5. Join: This node has two or more arcs entering and one exiting. A join is executed when it receives control from all entering arcs.

Thus, conditional behaviors are shown by decisions and merges, while parallel behaviors are shown by synchronization bars and joins. In a UML scheme, two state nodes are highlighted: the initial state and the final state. The diagram begins in the initial state and ends in the final state. Every node is reachable from the initial state, and from every node, the final state is reachable. A path is a sequence of nodes in the diagram. The entry of a node is the node whose exit arc enters the given node. The exit of a node is the node whose entry arc exits from the given node.

Some combinations of decisions and synchronization bars are difficult, or even impossible, to interpret on traditional von Neumann computational systems, as they can lead to potentially infinite numbers of parallel paths. Therefore, both the UML standard and most of its implementations define several constraints on the diagram's structure.

Your task is to write a program that reviews the diagram description and checks its correctness and compliance with the following constraints:

• Execution paths exiting a synchronization bar cannot pass through the same state, decision, or merge.

• Execution paths exiting a decision cannot pass through the same state, synchronization bar, or join.

• Each decision corresponds to a separate merge, where all possible execution paths starting at this decision end.

• Each synchronization bar corresponds to one join, where all execution paths starting at this synchronization bar end.

• The entries and exits of decision, synchronization bar, merge, and join nodes can only be states.

• The entries and exits of states can be any nodes.

• To simplify the diagram, one join may be specified for several synchronization bars, combining the paths of all corresponding synchronization bars.

• Similarly, a common merge may be specified for several decisions.

The activity diagram in the UML language is specified as follows. Each node of the diagram is marked with an integer (the node number). The type of node is indicated by an uppercase Latin letter:

S — state,

D — decision activity,

M — merge,

B — synchronization bar,

J — join.

An example of a simple activity diagram in the UML language is shown in the figure. In it, $0$ — initial state, $17$ — final state, $2$ and $10$ — synchronization bars, $14$ — join, $5$ — decision, $8$ — merge. All other nodes of the diagram are states.