Помогите придумать алгоритм к задаче

Деление на группы
Ограничение времени: 0.5 секунды
Ограничение памяти: 16 МБ


В детском саду N детей. К сожалению, дети иногда ссорятся, хотя и не часто. У каждого ребёнка есть не более трёх недругов. Можно ли разделить детей на две группы (не обязательно равные) так, чтобы у каждого ребёнка в одной с ним группе было бы не более одного неприятеля?

Исходные данные

В первой строке находится положительное число N, не превосходящее 7163. В последующих N строках указаны списки недругов для каждого из детей. В начале каждой строки указывается количество недругов для очередного ребёнка, затем перечисляются номера недругов. Числа в одной строке отделяются друг от друга пробелом.

Результат

В первой строке указывается количество детей в той из групп, которая содержит меньшее число детей. Затем во второй строке указывается список детей в этой группе. Числа во второй строке разделяются пробелом. Если в обеих группах одинаковое число детей, то следует выводить описание той, в которой оказывается ребёнок номер 1. Заметим, что вполне возможна ситуация, когда ответ состоит из единственного числа 0. Если возможных разбиений несколько, достаточно вывести любое из них. Если разбить детей на группы невозможно, то в первую строку следует вывести строку 'NO SOLUTION'.

Пример
исходные данные
8
3 2 3 7
3 1 3 7
3 1 2 7
1 6
0
2 4 8
3 1 2 3
1 6

результат
4
1 2 5 6

http://acm.timus.ru/problem.aspx?space=1&num=1128

Мне нужен алгоритм к этой задачи никак немогу придумать подскажите, брут-форс не предлагать ...

 

да уже решил давно вот код если интересно
// 1128. Деление на группы.

#include "stdafx.h"
#include <iostream>

using namespace std;

const int max_dimensionality_children = 7163;
const int max_quantity_enemies = 3;

int dimensionality_children;
int quantity_enemies[max_dimensionality_children];
int dimensionality_team;
int enemies[max_dimensionality_children][max_quantity_enemies];
int dimensionality_first_group;
int dimensionality_second_group;
int team[max_dimensionality_children];

bool first_group[max_dimensionality_children];
bool second_group[max_dimensionality_children];
bool flag_team[max_dimensionality_children];

int set(int, int);
int verification(int, bool, int);
int find_enemies(int, bool, int);
int change(int, bool, int);
int links(int);
int find_links(int);
int print_group(bool, int);

int set(int current_index, int comes_index)
{
if ((current_index == comes_index) || second_group[comes_index])
{
first_group[current_index] = 1;
dimensionality_first_group++;
}
else
{
second_group[current_index] = 1;
dimensionality_second_group++;
}
team[dimensionality_team] = current_index;
dimensionality_team++;
verification(current_index, 1, current_index);
links(current_index);
return 0;
}
int verification(int verification_index, bool verification_flag, int current_index)
{
bool flag_enemies;

int index;

flag_enemies = 0;

for (index = 0; index < quantity_enemies[verification_index]; index++)
{
if ((first_group[enemies[verification_index][index]] && first_group[verification_index]) || (second_group[enemies[verification_index][index]] && second_group[verification_index]))
{
if (flag_enemies)
{
change(verification_index, 0, current_index);
return 0;
}
flag_enemies = 1;
}
}
if (verification_flag)
find_enemies(verification_index, 0, current_index);
return 0;
}
int find_enemies(int find_enemies_index, bool verification_flag, int current_index)
{
int index;

for (index = 0; index < quantity_enemies[find_enemies_index]; index++)
{
if (first_group[enemies[find_enemies_index][index]] || second_group[enemies[find_enemies_index][index]])
verification(enemies[find_enemies_index][index], 0, current_index);
}
return 0;
}
int change(int change_index, bool verification_flag, int current_index)
{
if (first_group[change_index])
{
first_group[change_index] = 0;
dimensionality_first_group--;
second_group[change_index] = 1;
dimensionality_second_group++;
}
else
{
second_group[change_index] = 0;
dimensionality_second_group--;
first_group[change_index] = 1;
dimensionality_first_group++;
}
current_index = change_index;
find_enemies(current_index, 1, current_index);
return 0;
}
int links(int current_index)
{
int index;

if (flag_team[current_index])
find_links(current_index);
for (index = 0; index < dimensionality_team; index++)
{
if (flag_team[index])
find_links(index);
}
return 0;
}
int find_links(int current_index)
{
int index;

for (index = 0; index < quantity_enemies[current_index]; index++)
if (!first_group[enemies[current_index][index]] && !second_group[enemies[current_index][index]])
{
set(enemies[current_index][index], current_index);
return 0;
}
flag_team[current_index] = 0;
return 0;
}
int print_group(bool group[], int dimensionality_group)
{
int index;

cout << dimensionality_group;
if (dimensionality_group != 0)
cout << endl;
for (index = 0; index < dimensionality_children; index++)
if (group[index])
{
cout << index + 1;
dimensionality_group--;
if (dimensionality_group != 0)
cout << ' ';
else
break;
}
return 0;
}
int main(int argc, _TCHAR* argv[])
{
int index, second_index;

cin >> dimensionality_children;

for (index = 0; index < dimensionality_children; index++)
{
first_group[index] = 0;
second_group[index] = 0;
flag_team[index] = 1;
cin >> quantity_enemies[index];
for (second_index = 0; second_index < quantity_enemies[index]; second_index++)
{
cin >> enemies[index][second_index];
enemies[index][second_index]--;
}
}

dimensionality_first_group = 0;
dimensionality_second_group = 0;
dimensionality_team = 0;

index = 0;
do
{
if (!first_group[index] && !second_group[index])
{
set(index, index);
dimensionality_team = 0;
}
index++;
}
while (dimensionality_first_group + dimensionality_second_group != dimensionality_children);

if (dimensionality_first_group <= dimensionality_second_group)
print_group(first_group, dimensionality_first_group);
else
print_group(second_group, dimensionality_second_group);

cout << endl;
return 0;
}

добавлено через 20 минут
Да и кстати ответа 'NO SOLUTION' здесь не может быть...