Лабіринти Дейзі

Дейзі любить розслаблятися після важкого дня, гуляючи в лабіринтах. Лабіринти, які їй подобаються, складаються з кількох кімнат з однією вхідною та однією вихідною кімнатою. У кожній кімнаті є кілька односторонніх дверей, що ведуть до інших кімнат. Завдання Дейзі — знайти шлях від входу до виходу.

Дейзі має свій спосіб розв'язання лабіринтів. Вона помітила, що двері в кожній кімнаті мають різні кольори, і може запам'ятовувати свій шлях, відстежуючи кольори дверей. Перед входом у лабіринт вона вивчає план і складає колоду карт, що відповідають кольорам дверей, які їй потрібно пройти. Кожного разу, коли вона входить у кімнату, вона проходить через двері, колір яких відповідає кольору верхньої карти в її колоді, а потім викидає цю карту.

Іноді трапляється, що колода у Дейзі "неповна", і вона приходить у кімнату з порожньою колодою або з верхньою картою кольору, що не відповідає жодним з дверей. У таких випадках Дейзі проходить через одні з дверей у кімнаті і замість того, щоб викинути верхню карту, вона додає зверху своєї колоди карту кольору дверей, які вона обрала.

Розглянемо приклад лабіринту з трьома кімнатами і трьома дверима: червоні двері ведуть з входу в кімнату $1$, інші червоні двері ведуть з кімнати $1$ назад на вхід, і сині двері ведуть з кімнати $1$ до виходу. У цьому прикладі лабіринту (зображеному нижче):

• якщо Дейзі почне з колоди, що містить червону карту зверху і синю знизу, то вона піде в кімнату $1$, викине червону карту, потім піде до виходу і викине синю карту;

• якщо Дейзі почне з колоди, що містить одну червону карту, то як перший крок вона обов'язково піде в кімнату $1$, викине червону карту і звідти може обрати або сині двері і вийти (не має значення, чи буде її колода в кінці порожньою чи ні) або червоні двері і повернутися до початкової ситуації: на вхід з єдиною червоною карткою;

• якщо вона стартує або прибуває на вхід з порожньою колодою, то обов'язково буде зациклюватися на невизначений термін. Дійсно, на вході є тільки одні двері, що ведуть в кімнату $1$. Як тільки вона потрапляє в кімнату $1$, її колода зверху містить червону карту, тому їй доведеться взяти червоні двері і викинути цю карту, що приведе її назад у кімнату входу з порожньою колодою.

Дейзі знає, що у всіх своїх лабіринтах вона завжди може пройти з кімнати входу в кімнату виходу за допомогою потрібної колоди. Однак деякі колоди не дозволяють їй втекти, який би вибір вона не зробила. Вона задається питанням: який мінімальний розмір колоди, що дозволяє їй втекти? Дейзі дає вам план лабіринту і просить допомогти їй визначити мінімальний розмір колоди, який дозволить їй пройти від входу до виходу, якщо вона зробить правильний вибір.