Колега з пекла

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

Маючи доступ до такого графіка, його колега вирішив пожартувати й змусити сторожа затриматися в приміщенні якнайдовше. Для цього колега може встановити кілька «пасток» у деяких кімнатах до приходу сторожа. Кожна пастка в певній кімнаті змушує сторожа подумати, що в іншій кімнаті щось відбувається, і, відповідно, він проведе в цій кімнаті інший проміжок часу та попрямує до нової кімнати, яка може не збігатися зі звичайним маршрутом. Потрапивши у нову кімнату, сторож продовжує огляд за стандартним порядком (і можливо, він не потрапить у деякі кімнати). Наприклад, якщо є п’ять кімнат, які зазвичай оглядають послідовно, а єдина пастка встановлена у кімнаті $2$ і вона веде до кімнати $4$, маршрут виглядає так: 1 - 2 - 4 - 5, після чого сторож іде додому. Пастка спрацьовує лише під час першого візиту до кімнати і не діє надалі. За цією інформацією слід скласти програму, що допоможе колезі спланувати пастки так, щоб сторож затримався на заводі якнайдовше.

1
5
2 99 4
2 2 3
2 2 4
2 2 5
2 2 5

105