Інфільтрація#3391
Добрий ранок, агенте W-12. Ваша місія, якщо ви вирішите її прийняти, полягає в наступному.
Ми проникаємо в надзвичайно підступну Асоціацію Хаосу та Пустощів (АХП), щоб знищити їхню командну структуру. На жаль, вони, здається, підготувалися до такої можливості і надали своїй командній структурі дратівливо складний дизайн, що робить наше проникнення досить складним.
Командна структура АХП поділена на кілька осередків. Для кожної пари осередків та , або контролює , або контролює . Але це відношення контролю може бути циклічним, тому може статися так, що контролює , контролює , а контролює .
Ми можемо відправити агентів для проникнення в будь-який конкретний осередок, що дає нам контроль над цим осередком і осередками, які він контролює, але не над іншими осередками. Отже, в наведеному прикладі, проникнення в дало б нам контроль над і , але не над .
Для успішного проникнення в АХП ми повинні отримати контроль над усіма її осередками, інакше осередки, які залишатимуться поза нашим контролем, виявлятимуть нас і почнуть спричиняти свій фірмовий хаос і пустощі. Як ви знаєте, ми зараз на жорсткому фінансовому обмеженні від вищого керівництва, тому нам потрібно виконати цю місію якомога ефективніше. Ваше завдання — визначити мінімальну кількість осередків, в які ми повинні проникнути, щоб досягти успіху.
Цей брифінг самознищиться через п'ять годин. Удачі!
Перша строка тестового випадку містить число осередків, які має АХП (1 \leq n \leq 75). Кожен з наступних рядків містить бінарний рядок довжиною , де -й символ -го рядка є , якщо осередок контролює осередок , і в іншому випадку (1 \leq i, j \leq n).
-й символ -го рядка є і для i \neq j, або -й символ -го рядка є , або -й символ -го рядка є , але не обидва.
Для кожного тестового випадку виведіть номер випадку, за яким слідує мінімальне число осередків, в які потрібно проникнути, щоб отримати повний контроль над АХП. Потім виведіть чисел c_1, \ldots, c_m в будь-якому порядку, що вказують на список осередків для проникнення (осередки нумеруються від до ). Якщо більше ніж один набір з осередків дає повний контроль, будь-який з них буде прийнятий.
Приклад 1