Приватизация

Помогите решить задачу несколько дней сижу голову ломаю нифига не получается (если не затруднит можно с комментариями хотелось бы разобраться во всем этом деле)
Задача 6. Приватизация

Имя входного файла rail.in

Имя выходного файла rail.out

Время тестирования 20 секунд

Железнодорожная сеть состоит из отдельных участков, соединяющих города попарно. Этими участками каждый из N имеющихся городов соединен с тремя другими городами. Две компании собираются приватизировать все эти участки, но антимонопольный комитет настаивает на том, чтобы из каждого города выходили дороги разных компаний.

Напишите программу, которая распределяет все участки между компаниями с соблюдением вышеназванного требования или сообщает, что этого сделать невозможно.

Входные данные

В первой строке входного файла содержится натуральное число N — количество городов (N≤5000) Далее для каждого города i (i=1,…,N) записана тройка различных чисел — номера тех городов, с которыми он связан. Соединение городов i и j, если оно существует, отражено в соответствующих строках. Между любыми двумя городами может проходить не более одной дороги.

Выходные данные

В выходной файл требуется вывести список участков, предназначенных для приватизации одной из компаний (все остальные участки приватизируются другой компанией). Каждый участок задается в отдельной строке двумя числами — номерами тех городов, которые он соединяет. Числа должны разделяться пробелами. Если решения не существует, выходной файл должен содержать единственную строку “NO SOLUTION”.

Пример входного файла rail in

6
6 5 3
6 4 3
4 1 2
5 3 2
6 4 1
2 1 5

Пример выходного файла rail.out

1 6
2 4
3 4
5 6

0