Проста умова#12879

Проста умова

1,5 секунди
256 мегабайтів
Складна

Вам дано неорієнтований граф на вершинах. Для кожної пари вершин (i\neq j), визначте, чи існує Гамільтонів шлях, що починається в , а закінчується в .

Нагадаємо, що Гамільтонів шлях  — це шлях, що складається з n-1 ребер, що проходить по всім вершинам рівно по одному разу.

Вхідні дані

Перший рядок містить одне ціле число (2 \le n \le 24)  — кількість вершин в графі.

-ий з наступних рядків містить бінарний рядок s_i довжини . Його -ий символ завжди рівний 0, а для j\neq i його -ий символ рівний , якщо між вершинами та є ребро, і 0, якщо немає.

Гарантується, що для довільних i\neq j -ий символ -го рядка співпадає з -им символом -го рядка.

Вихідні дані

Виведіть рядків. В -му з них виведіть бінарний рядок довжини . Його -ий символ має бути рівним 0, а -ий при j\neq i має бути рівним 1, якщо між вершинами та є Гамільтонів шлях, і 0, якщо немає.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading

Примітка

В першому прикладі, Гамільтонів шлях є між парами та .

В другому прикладі, граф це цикл довжини . Гамільтонів шлях тут є лише між парами сусідніх вершин.

В третьому прикладі ми маємо повний граф на вершинах. Гамільтонів шлях тут є між кожною парою вершин.