Друзья - 2
(Время: 1 сек. Память: 16 Мб Сложность: 51%)
Несколько человек решили поехать отдохнуть на природе, подышать свежим воздухом и т.п. Как это часто бывает, некоторые из них дружат друг с другом, а некоторые - нет. Для того, чтобы не испортить никому настроение, они решили разделиться на несколько групп. При этом, в каждой группе должно быть не более 5 человек и они должны дружить друг с другом.
Найдите такое разбиение людей на группы, в котором размер наибольшей группы был бы максимальным (среди всех разбиений).
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число n (1 ≤ n ≤ 15) - количество людей. Следующие n строк содержат по n чисел. Если i-ый и j-ый люди дружат, то j-ое число i + 1-ой строки равно 1, иначе - 0.
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите число групп. Во второй строке выходного файла выведите n чисел (i-ое число - номер группы, в которой находится i-ый человек). Нумеруйте группы целыми числами от 1 до числа групп. Если решений несколько, то выведите любое.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
1 1 0
1 1 0
0 0 1 | 2
1 1 2 |
| 2 | 8
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 | 3
1 1 1 1 1 2 2 3 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
