Однажды Петя — очень храбрый исследователь — решил заняться изучением великих парижских катакомб. Так как Петя не очень опытный в этом деле, его исследование заключается в хождении по катакомбам.

Катакомбы представляют из себя набор комнат, некоторые из которых соединены переходами, переход может соединять комнату с самой собой, по переходам можно ходить в любую сторону. Переходы могут находиться на разных глубинах, что позволяет им не пересекаться. Каждую минуту Петя выбирает произвольным образом переход из комнаты, в которой он находится, и проходит его за одну минуту. Когда он заходит в комнату в минуту i, он делает в журнал запись — число t_i:

• Если Петя уже был в этой комнате, он записывает минуту, когда он был в этой комнате в предыдущий раз;
• Иначе Петя записывает в журнал произвольное неотрицательное целое число, строго меньшее текущей минуты i.

Изначально Петя находился в какой-то из комнат в минуту 0, при этом число t₀ он не записывал.

В какой-то момент Петя устал, бросил журнал и пошёл домой (не обязательно в той же комнате, из которой он начинал). Вася нашёл этот журнал, и теперь ему интересно: какое наименьшее количество комнат может быть в катакомбах, согласно журналу Пети?