Подготовка экспедиции на Марс

N кандидатов готовятся к двум космическим экспедициям на Марс. Поскольку экспедиции будут продолжаться несколько лет, а их участники окажутся в замкнутом пространстве небольшого объёма, то важное значение приобретает психологическая совместимость членов экипажа. Путём тестирования были установлены пары кандидатов, присутствие которых в одной и той же экспедиции было бы нежелательным. Результаты тестирования отражены в таблице размера N?N. Если на пересечении ii-той строки и jj-го столбца таблицы находится знак «+», то участие ii-го и jj-го кандидатов в одной экспедиции нежелательно. Составьте программу, разделяющую кандидатов на две группы для участия в экспедициях. Если такое разделение невозможно, программа должна выводить сообщение «No solution». В противном случае, программа должна выводить номера кандидатов, принадлежащих первой группе. Первой группой мы будем считать группу, в которой меньше кандидатов. Естественно, хорошо написанная программа должна стремиться к тому, чтобы размеры групп не очень сильно отличались. Поэтому, если возможно несколько разбиений на группы, программа должна выбирать разбиение с минимальной разностью количеств кандидатов в группах. При этом в случае, если разбиений с минимальной разницей всё равно получается несколько, для определённости выбирается разбиение, в котором первая группа лексикографически меньше, чем первые группы остальных разбиений. Java -- язык реализации, точкой входа в программу должен являться метод main класса Mars. Программа должна считывать со стандартного потока ввода количество кандидатов и матрицу размера N?N Входные данные 1: 2 - - - - 2: 3 - - - - - + - + - 3: 4 - - + - - - - - + - - - - - - - 4: 5 - - - - - - - - - - - - - - + - - - - - - - + - - 5: 6 - - - - - - - - - - - - - - - + + - - - + - + - - - + + - - - - - - - - 6: 7 - - - - + - - - - - - - - - - - - - - + - - - - - - - - + - - - - + - - - + - + - - - - - - - - - 7: 8 - - - - - - - - - - - - - - - - - - - - - + - - - - - - - - - - - - - - - - - + - - + - - - - - - - - - - - - - - - - - + - - - Выходные данные: 1: 1 2: 2 3: 1 2 4: 1 3 5: No solution 6: 1 2 6 7: 1 2 3 5