Задачи
Расписание работы
Расписание работы
Некоторое количество ночных охранников защищают местную свалку от возможных нежелательных грабежей. Этих охранников необходимо разбить на пары, так чтобы каждая пара дежурила в разные ночи. Генеральный директор свалки попросил Вас написать программу, которая по заданным характеристикам охранников определит максимально необходимое их количество (остальные охранники будут уволены). Отметим, что каждый охранник может работать только с одним из своих коллег, а также ни один из охранников не может работать в одиночку.
\InputFile
Первая строка содержит количество ночных охранников \textbf{N} ≤ \textbf{222}. Следующие строки представляют собой неупорядоченные пары (\textbf{i}, \textbf{j}), каждая из которых означает тот факт, что охранники \textbf{i} и \textbf{j} могут работать вместе, поскольку можно найти униформу подходящую для их обоих (на свалке используется разная униформа для разных охранников - шлемы, брюки, куртки. Невозможно надеть маленький шлем на охранника с большой головой или большие туфли на охранника с маленькими ногами). Входные данные заканчиваются концом файла.
\OutputFile
Вам следует вывести одно из возможных оптимальных распределений охранников. В первой строке следует вывести четное число \textbf{C} - количество требуемых охранников. Далее следует вывести \textbf{C/2} строк, каждая из которых содержит \textbf{2} целых числа (\textbf{i}, \textbf{j}), указывающие на то что охранники \textbf{i} и \textbf{j} будут работать вместе.
Входные данные #1
3 1 2 2 3 1 3
Выходные данные #1
2 1 2