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