Розрізання графа

Розбийте множину вершин заданого графа на дві непорожні підмножини A та B так, щоб кількість ребер між вершинами різних підмножин була мінімальною.

Вхідні дані

У першому рядку записано число вершин n (2 ≤ n ≤ 50) у графі. Кожен з наступнх n рядків містить по n символів. i-ий символ j-ого з цих рядків дорівнює "1", якщо між вершинами i та j є ребро, і "0" у протилежному випадку. Задана таким чином матриця суміжності графа є антирефлексивною (на головній діагоналі стоять нули) і симетричною (відносно головної діагоналі).

Вихідні дані

Виведіть два рядки. У першому виведіть номери вершин, які потрапили у множину A, через пропуск, а у другому - номери вершин, які потрапили у множину B, також через пропуск. Номери вершин можна виводити у довільному порядку.

Приклади