Однажды Петя — очень храбрый исследователь — решил заняться изучением великих парижских катакомб. Так как Петя не очень опытный в этом деле, его исследование заключается в хождении по катакомбам.
Катакомбы представляют из себя набор комнат, некоторые из которых соединены переходами, переход может соединять комнату с самой собой, по переходам можно ходить в любую сторону. Переходы могут находиться на разных глубинах, что позволяет им не пересекаться. Каждую минуту Петя выбирает произвольным образом переход из комнаты, в которой он находится, и проходит его за одну минуту. Когда он заходит в комнату в минуту i, он делает в журнал запись — число ti:
- Если Петя уже был в этой комнате, он записывает минуту, когда он был в этой комнате в предыдущий раз;
- Иначе Петя записывает в журнал произвольное неотрицательное целое число, строго меньшее текущей минуты i.
Изначально Петя находился в какой-то из комнат в минуту 0, при этом число t0 он не записывал.
В какой-то момент Петя устал, бросил журнал и пошёл домой (не обязательно в той же комнате, из которой он начинал). Вася нашёл этот журнал, и теперь ему интересно: какое наименьшее количество комнат может быть в катакомбах, согласно журналу Пети?
Примечание
В первом тестовом примере последовательность комнат, по которым прошёл Петя, могла быть 1 → 1 → 2 или 1 → 2 → 1, или, например, 1 → 2 → 3. Минимальное число комнат равно 2.
Во втором тестовом примере эта последовательность могла быть 1 → 2 → 3 → 1 → 2 → 1.