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

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

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

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

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

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

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

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

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

Вхідні дані

Перша рядок містить три цілі числа $r,d$ і $c(2\le r\le 50,2\le d\le 100,2\le c\le 20)$. Тут $r$ — кількість кімнат, $d$ — кількість дверей, а $c$ — кількість кольорів. Кімнати пронумеровані з $0$ до $r-1$, а кольори з $0$ до $c-1$.

Кожна з наступних $d$ рядків описує двері з трьома цілими числами $f,t$ і $col$, такими що $0\le f\le r-1,0\le t\le r-1,f\ne t$ і $0\le col\le c-1$. Це вказує на те, що двері з кімнати $f$ ведуть у кімнату $t$, і що у цих дверей колір $col$.

Вихідні дані

Виведіть одне ціле число: мінімальне ціле число $s$ таке, що існує колода, що складається з $s$ карт, яка дозволяє Дейзі, якщо вона зробить правильний вибір, пройти від входу (кімната з номером $0$) до виходу (кімната з номером $r-1$).

Приклади

Приклад $1$.

• Дейзі починає свій шлях у кімнаті $0$ з порожньою колодою

• Вона йде в кімнату $1$ з картою $0$ в колоді

• Вона йде в кімнату $2$ з порожньою колодою

• Вона йде в кімнату $0$ з картою $0$ в колоді

• Вона йде в кімнату $1$ з порожньою колодою

• Тепер у неї є можливість зробити вибір: піти до виходу.

Приклад $2$. Цей приклад наведено в тексті задачі, де червоний колір представлений як $1$, а синій як $0$.