Синтаксис UML
UML (Unified Modelling Language) - унифицированный язык моделирования, который применяется для разработки сложных объектно-ориентированных программных проектов. Одним из элементов UML является диаграмма деятельности, предназначенная для описания алгоритмов поведения взаимодействующих параллельных процессов.
В простейшем случае диаграмму деятельности можно представить схемой, состоящей из вершин и дуг. Каждая вершина соответствует некоторой деятельности языка, а дуга - передаче управления между двумя вершинами.
Назовем схему правильной, если она состоит из вершин следующих пяти видов:
Состояние. В такой вершине выполняется некоторое действие. Она имеет не более одной входящей дуги и не более одной выходящей.
Ветвление. Эта вершина имеет одну входящую дугу и две или более выходящих. Каждой выходящей дуге соответствует некоторое условие, причем из всех условий только одно должно быть истинно. По дуге, которой соответствует истинное условие, передается управление.
Слияние. Вершина этого вида имеет две или более входящих дуг и одну выходящую. Слияние означает окончание нескольких вариантов условного поведения, которые были начаты соответствующим ветвлением.
Разделение. Такая вершина имеет одну входящую дугу и не менее двух выходящих. Она предназначена для описания параллельного поведения системы. При исполнении разделения управление передается по всем выходящим дугам.
Соединение. Эта вершина имеет две или более входящих дуг и одну выходящую. Соединение исполняется, если оно получает управление по всем входящим дугам.
Таким образом, условное поведение изображается с помощью ветвлений и слияний, а параллельное поведение - с помощью разделений и соединений. В UML-схеме выделены две вершины вида состояние: начальная и конечная. Функционирование диаграммы начинается в начальном состоянии и заканчивается в конечном. Каждая вершина достижима из начального состояния и из каждой вершины достижимо конечное состояние. Путь - это последовательность вершин в диаграмме. Входом вершины назовем такую вершину, у которой выходящая дуга входит в данную вершину. Выходом вершины назовем такую вершину, у которой входящая дуга выходит из данной вершины.
Некоторые сочетания ветвлений и разделений сложно или даже невозможно интерпретировать на традиционных фон-неймановских вычислительных системах. Одной из причин является то, что они порождают потенциально бесконечное количество параллельных путей. Поэтому и стандарт UML, и большинство его реализаций определяют различные ограничения на структуру диаграммы.
Ваша задача - написать программу, которая просматривает описание диаграммы и проверяет ее правильность и соответствие следующим ограничениям:
Пути исполнения, вышедшие из разделения, не могут проходить через одно и то же состояние, ветвление или слияние.
Пути исполнения, вышедшие из одного ветвления, не могут проходить через одно и то же состояние, разделение или соединение.
Каждому ветвлению соответствует отдельное слияние, в котором заканчиваются всевозможные пути исполнения, начавшиеся в этом ветвлении.
Каждому разделению соответствует одно соединение, в котором заканчиваются все пути исполнения, начавшиеся в этом разделении.
Входы и выходы вершин вида ветвление, разделение, слияние и соединение могут быть только состояниями.
Входы и выходы состояний могут быть любыми вершинами.
Для упрощения диаграммы разрешается для нескольких разделений указывать одно соединение, объединяющее все пути соответствующих разделений.
Аналогично, для нескольких ветвлений можно указывать одно общее слияние.
Диаграмма деятельности языка UML задается следующим образом. Каждая вершина диаграммы помечается целым числом - номером вершины. Вид вершины обозначается большой латинской буквой:
S - состояние (State),
D - ветвление (Decision Activity),
M - слияние (Merge),
B - разделение (Synchronization Bar),
J - соединение (Join).
Пример простой диаграммы деятельности языка UML приведен на рисунке. В нем 0 - начальное состояние, 17 - заключительное, 2, 10 - разделение, 14 - соединение, 5 - ветвление, 8 - слияние. Все остальные вершины диаграммы - состояния.
Входные данные
В первой строке входного файла указано целое число N (N <= 10000) - количество элементов диаграммы. Вершины диаграммы пронумерованы числами от 0 до N - 1. Начальное состояние имеет номер 0, а заключительное - (N - 1). В каждой из следующих N строк описываются по порядку вершины диаграммы, по одной на строке. Описание одной вершины содержит в первой позиции строки один символ - вид вершины, а далее (в зависимости от вида вершины) может следовать информация о входах и выходах. Для начального состояния указан только номер выхода, а для заключительного - только номер входа. Для всех состояний, кроме начального и заключительного, указан сначала номер входа, и затем номер выхода. Для остальных видов вершин дополнительная информация отсутствует.
Выходные данные
В результирующий файл вы должны вывести строку CORRECT, если диаграмма правильная и соответствует всем оговоренным в условии ограничениям. В противном случае необходимо вывести строку INCORRECT