Синтаксис UML
UML (Unified Modelling Language) - уніфікована мова моделювання, яка застосовується для розробки складних об'єктно-орієнтованих програмних проектів. Одним з елементов UML є діаграма діяльності, призначена для опису алгоритмів поведінки взаємодіючих паралельних процесів.
У найпростішому випадку діаграму діяльності можна представити схемою, що складається з вершин та дуг. Кожна вершина відповідає деякій діяльності мови, а дуга - передачі керування між двома вершинами.
Назвемо схему вірною, якщо вона складається з вершин наступних п'яти видів:
1. Стан. В такій вершині виконується деяка дія. Вона має не більше однієї дуги, що входить у неї, і не більше однієї, що виходить.
2. Розгалуження. Ця вершина має одну дугу, що входить, і дві або більше, що виходять. Кажній дузі, що виходить, відповідає деяка умова, причому з усіх умов тільки одна повинна бути істинною. По дузі, якій відповідає істинна умова, передается керуавання.
3. Злиття. Вершина цього виду має дві або більше дуг, що входять, і одну, що виходить. Злиття означає закінчення декількох варіантів умовної поведінки, які були розпочаті відповідним розгалуженням.
4. Розподіл. Така вершина має одну дугу, що входить, і не менше двох, що виходять. Вона призначена для опису паралельної поведінки системи. При виконанні розподілу керування передається по всім дугам, що виходять.
5. З'єднання. Ця вершина має дві або більше дуг, що входять, і одну, що виходить. З'єднання виконується, якщо воно отримує керування по всім дугам, що входять.
Таким чином, умовна поведінка зображається при допомозі розгалужень і злиттів, а паралельна поведінка - при допомозі разподілів і з'єднань. В 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
.