Компьютерная сеть состоит из связанных между собой двусторонними каналами связи N компьютеров, номера которых от 1 до N. Эта сеть предназначена для распространения сообщения от центрального компьютера всем остальным. Компьютер, получивший сообщение, владеет им и может распространять его дальше по сети. Запрещается передавать сообщение на один и тот же компьютер дважды. Время передачи сообщения по каналу связи занимает одну секунду, при этом передающий и принимающий компьютеры заняты на все время передачи данного сообщения. На рисунке приведен возможный вариант такой сети.

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

Для сети, показанной на рисунке, возможный порядок распространения сообщения от центрального компьютера с номером 6 приведен в примере.

Пример

Секунда 1: 6->4 
Секунда 2: 4->3 
6->7 
Секунда 3: 3->1 
4->5
Секунда 4: 3->2 

Написать программу, которая:

1. вводит описание сети, проверяет корректность этого описания и, в случае его некорректности, печатает соответствующее сообщение, заканчивая работу
2. определяет и печатает какой-либо порядок распространения сообщения;
3. определяет и печатает порядок передачи сообщения за минимальное время (порядок распространения сообщения для сети на рисунке приведенный в примере, является оптимальным).

1. N не превосходит 50, а количество каналов связи не превосходит N+5.
2. Программа должна запрашивать имя входного файла; в крайнем случае допускается ввод данных с клавиатуры.
3. Сеть задается набором из N+2 строк в следующем формате:
   • строка 1: число компьютеров в сети (N);
   • строка 2: список всех соседей компьютера 1 (представляется набором чисел, разделенных пробелами);
   • строка 3: список всех соседей компьютера 2;
   • ...
   • строка N+1: список всех соседей компьютера N;
   • строка N+2: номер центрального компьютера.
   Так, приведенная на рисунке сеть может быть представлена следующим образом:

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

4. Вывод результатов на экран должен быть таким, как в примере.

1. Организация диалога с пользователем: - 5 баллов.
2. Пункт А: - 25 баллов.
3. Пункт B: - 25 баллов.
4. Пункт C: - 30 баллов.
5. Выполнение технических требований: - 15 баллов.