• Переправа через реку
  FERRY

Описание
Жителю Аляски Джону по дороге в ближайший город надо переправиться через широкую незамерзающую реку. Для этого Джон поступает очень просто - запрягает своих собак в сани, цепляет к саням лодку и отправляется в путь. Подъехав к реке, Джон садится в лодку и перевозит через реку всех собак. В один из переездов через реку Джон привязывает к лодке сани, и в итоге Джон со всеми собаками и санями успешно переправляется через реку.

Однако не все так просто, как может показаться - некоторые собаки, когда Джона нет рядом, ссорятся между собой, и во время переправы через реку их нельзя оставлять на одном берегу без присмотра. В свою очередь, собак, которые между собой не ссорятся, можно смело оставлять на одном любом берегу и ничего плохого при этом не происходит. К счастью, Джон знает, какие собаки не ладят между собой.

Допустим, что у Джона в упряжке пять собак - Вихрь, Мишка, Чудак, Злой и Арго. Мишка враждует с Вихрем, Злым и Арго. Чудак враждует с Вихрем и Злым. Другие собаки между собой не враждуют. Тогда Джону достаточно иметь трехместную лодку, т.е. такую, чтобы пересекая реку один раз, он мог перевезти двух собак. При этом (с трехместной лодкой) минимально требуется пересечь реку 7 раз (каждая собака занимает одно место, сани места не занимают): 

1. Перевезти Мишку и Чудака;
2. Перевезти Мишку обратно;
3. Перевезти Арго и Мишку; 
4. Перевезти Мишку и Чудака обратно;
5. Перевезти Злого и Вихря; 
6. Обратно приехать пустым;
7. Перевезти Мишку и Чудака и продолжать путь. 

Ни в какой момент два враждующих между собой пса не оставались на одном берегу без присмотра. Однако, если, например, еще поссорятся Арго и Вихрь, то тогда трехместной лодки не хватит. 

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


Входные данные
В первой строке файла FERRY.DAT находится одно натуральное число N (1<=N<=10) - количество собак в упряжке. Будем считать, что собаки пронумерованы числами 1,2,3,…,N. Вторая строка содержит целое неотрицательное число K - количество пар враждующих между собой псов. Каждая из следующих K строк содержит по одной паре враждующих между собой собак в форме "a b", где a и b - номера собак (1<=a<=N, 1<=b<=N, a<>b). Номера в строке разделены пробелом

В файле все пары враждующих между собой собак указаны ровно по одному разу. Паре враждующих собак отвечает и запись "a b", и запись "b a", но в файле представлена только одна из них.

Выходные данные
Первая строка файла FERRY.REZ должна содержать одно натуральное число X - наименьшее количество мест в лодке, необходимое для того, чтобы перевезти собак через реку так, как описано выше. Во второй строке должно находиться одно натуральное число Y- количество пересечений реки, необходимое для того, чтобы перевезти всех собак в X-местной лодке. В каждой из следующих Y строк должно стоять описание одного пересечения реки (в том порядке, в каком эти пересечения следует исполнять). (i+2)-я строка файла описывает i-й переезд и имеет вид:

a₁ a₂ a₃ … a_j 0

где a₁ a₂ a₃ … a_j - номера собак, которых надо перевозить при i-ом переезде через реку. Номера должны идти в возрастающем порядке. Соседние числа следует отделять пробелом. Каждая строка должна заканчиваться 0, отделенным от последнего номера пробелом. Переезд с пустой лодкой обозначается строкой, содержащей только символ 0


Например:

FERRY.DAT
5
5
1  2
2  3
4  3
4  5
2  5 


FERRY.REZ
3
7
2  4  0
2  0
1  2  0
2  4  0
3  5  0
0
2  4  0