Кольори
Менеджер компанії з виробництва іграшок прагне знизити витрати на виготовлення своєї продукції. Іграшки створюються за допомогою роботів, які працюють на складальних лініях, додаючи та з'єднуючи компоненти в модулі, а також об'єднуючи існуючі модулі в більш складні конструкції. Компоненти можуть бути або активними, або неактивними. У будь-який момент часу на кожній доріжці та в кожному модулі є рівно один активний компонент; це єдиний компонент, який може бути з'єднаний або об'єднаний на цій доріжці для цього модуля.
Новий бюджет компанії дозволяє використовувати лише компоненти, що складаються з трьох кольорів, і суміжні компоненти повинні мати різні кольори. Ваше завдання — визначити, які з поточних іграшок в інвентарі можуть бути виготовлені з цим обмеженням на кольори.
Компанія використовує наступний формалізм BNF для точного опису креслень своїх іграшок:
1. <іграшка> ::= <остання-доріжка><модуль>
Поточна <іграшка> складається з основного <модуля>. <остання-доріжка> вказує номер останньої доріжки, використаної для побудови поточної <іграшки>; доріжки нумеруються від 0 до <остання-доріжка>.
2. <модуль> ::= '(' <послідовність-операторів> ')'
<модуль> представляє простий модуль, що містить лише оператори. Оператори, задані <послідовність-операторів>, обробляються зліва направо.
Цей <модуль> починається з порожніх доріжок, а потім автоматично додає один активний компонент на кожну з доступних доріжок.
3. <об'єднаний-модуль> ::= '(' <модуль>_1<модуль>_2 ')'
Це операція об'єднання, яка створює складний <об'єднаний-модуль> шляхом об'єднання активних компонентів <модуль>_1 та <модуль>_2, після того як обидва модулі повністю побудовані.
4. <модуль> ::= '(' <об'єднаний-модуль><послідовність-операторів> ')'
Компоненти <об'єднаний-модуль> залишаються на доріжках, і його активні компоненти далі обробляються операторами, заданими <послідовність-операторів>.
5. <послідовність-операторів> ::= λ | <оператор><послідовність-операторів>
6. <оператор> ::= <оператор-вузла> | <оператор-ребра>
7. <оператор-вузла> ::= <номер-доріжки>
<оператор-вузла> додає активний компонент на вказану <номер-доріжки> для поточного модуля, а попередній активний компонент на цій доріжці стає неактивним.
8. <оператор-ребра> ::= <пара-номерів-доріжок>
<оператор-ребра> з'єднує активні компоненти двох номерів доріжок.
Наступні приклади демонструють кілька простих креслень іграшок; на малюнках доріжки представлені як горизонтальні пунктирні лінії, компоненти як кола, з'єднання як суцільні лінії, а вісь часу йде зліва направо.
Приклад 1 Рисунок 1 зображує 3-колірну іграшку, яку можна побудувати за допомогою наступного креслення:
2 ( 20 10 21 2 20 )
Рисунок 1: 3-колірна іграшка
Є 3 доріжки, пронумеровані 0, 1, 2. Іграшка складається з одного модуля, що містить 4 компоненти, позначені a, b, c, d, з'єднані лініями c–a, b–a, c–b, d–a. Щоб побудувати цю іграшку, робот виконає в порядку наступні операції:
Додати a на доріжку 0, b на доріжку 1, c на доріжку 2. На цьому етапі a, b і c є активними компонентами.
Зробити з'єднання c–a, b–a і c–b.
Додати d на доріжку 2, що робить d активним і деактивує c.
Зробити з'єднання d–a. На цьому етапі a, b і d є активними компонентами.
Зверніть увагу, що ту ж іграшку можна також побудувати, використовуючи кілька інших креслень, таких як наступні два:
2 ( 10 20 21 2 20 )
2 ( ( ( 20 10 ) ( 21 ) ) 2 20 )
Приклад 2 Рисунки 2 і 3 ілюструють послідовність операцій, що включають об'єднання, для іншої 3-колірної (навіть 2-колірної) іграшки, яку можна побудувати, як зазначено в наступному кресленні:
1 ( ( ( 10 1 10 0 ) ( 10 1 10 0 ) ) 10 1 10 )
1. Спочатку будується модуль 1:
(a) Додати a на доріжку 0 і b на доріжку 1.
(b) З'єднати b–a.
(c) Додати c на доріжку 1.
(d) З'єднати c–a.
(e) Додати d на доріжку 0. c і d тепер є активними компонентами модуля 1.
2. По-друге, модуль 2 будується за допомогою подібних операцій. g і h тепер є активними компонентами модуля 2.
3. По-третє, модулі 1 і 2 об'єднуються разом, що означає, що активні компоненти кожної доріжки ідентифікуються, тобто c = g і d = h. Знімок Рисунка 2 ілюструє цей момент, з дужками, що показують ідентифікацію компонентів. (c + g) і (d + h) тепер є активними компонентами об'єднаного модуля 1 + 2.
4. По-четверте, щойно об'єднані компоненти з'єднуються, тобто (c + g)–(d + h).
5. Нарешті, i додається на доріжку 1 і з'єднується з (d+h). Кінцевий результат зображено на Рисунку 3, а з'єднання, зроблені після об'єднання, зображені подвійними лініями. В кінці i і (d+h) є активними компонентами основного модуля.
Вхідні дані
Вхідні дані складаються з послідовності креслень іграшок, по одному на рядок, довжиною не більше 250 символів. Кожне креслення іграшки містить послідовність токенів, розділених одиночними пробілами, і відповідає правилам BNF, зазначеним раніше.
Перший токен - це додатне ціле число t, 0 ≤ t ≤ 6, що позначає максимальний номер доріжки, яку можуть захопити руки робота (тобто є t + 1 поточних компонентів для робота).
Вхідні дані завершуються описом іграшки з t = 0, яка не обробляється.
Вихідні дані
Необхідний вихід - це рядок у формі "Іграшка #: ?", де # позначає номер іграшки в послідовності, починаючи з 1, а ? - це або Так, або Ні, в залежності від того, чи може іграшка бути правильно побудована, використовуючи не більше 3 кольорів.