eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Робота для роботів

Робота для роботів

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

На планеті PTZZZ живе і працює n роботів. З незапам'ятних часів деякі роботи дружать між собою, а деякі — ні.

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

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

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

Вхідні дані

У першому рядку записано ціле число n, кількість роботів на PTZZZ (1n50). У кожному з наступних n рядків записано по n цифр 0 або 1. j-та цифра у i-му рядку дорівнює одиниці, якщо i-й та j-й роботи дружать між собою, і нулю у протилежному випадку. Гарантується, що i-та цифра у i-му рядку рівна нулю, а j-та цифра у i-му рядку співпадає з _i-тою цифрою у j-му рядку.

Вихідні дані

Виведіть номер дня, у який робот-директор буде змушений заіржавіти від горя.

Приклад

Вхідні дані #1
6
011100
101100
110100
111000
000001
000010
Вихідні дані #1
19
Автор М.Колодяжний, О.Самсонов
Джерело Ural SU Contest. Petrozavodsk Winter Session, February 2009