Руководитель одной организации решил создать эффективную систему оповещения своих сотрудников на случай возникновения экстраординарной ситуации. Для этого он разбил всех сотрудников на несколько групп следующим образом. В первую группу вошли сотрудники, номера телефонов которых он сам знал, во вторую - сотрудники, номера телефонов которых в целом знали сотрудники первой группы и т.д. В результате этого получилась схема подобная изображенной на рисунке. Цифры в этой схеме означают номера сотрудников (цифра 1 - руководителя), а стрелки определяют знание сотрудником номера телефона другого сотрудника.
Система оповещения должна функционировать следующим образом. В случае возникновения экстраординарной ситуации руководитель должен последовательно позвонить всем сотрудникам первой группы. Сотрудник, получивший сообщение, должен позвонить по известным ему телефонам сотрудникам другой группы и т.д. В результате этого каждый сотрудник организации должен быть проинформирован по телефону о наступлении экстраординарной ситуации, причем ему могли звонить только один раз. Во время передачи сообщения длительность телефонного разговора у всех сотрудников одинаковая и равна 1 минуте. В зависимости от того, кто кому и когда звонит, общее время оповещения всех сотрудников будет разным. Например, если для изображенной на рисунке схемы будет использоваться последовательность звонков, представленная в таблице А, то это время будет равно 4 минутам, а если в таблице В, то - 5 минутам. Руководителю необходимо знать такую последовательность звонков, которая обеспечивает полное оповещение за минимальное время.
Таблица А
|
Таблица В
|
В первой строке входного файла INPUT.TXT содержится целое число N (N Ј 20) - количество всех сотрудников в организации. Последующие N строк содержат описание схемы взаимодействия сотрудников, при этом каждая i-ая строка содержит число i - номер соответствующего сотрудника и номера сотрудников, телефоны которых известны i-му сотруднику. Все числа в строке разделены одним пробелом.
Выходной файл OUTPUT.TXT должен содержать в первой строке одно число - общее время оповещения всех сотрудников в минутах. В каждой из последующих строк должны содержаться пары чисел (номер источника и номер получателя), соответствующие передачи сообщения по телефону в один и тот же период времени. Все числа в каждой строке разделены одним пробелом.
| Пример INPUT.TXT: | OUTPUT.TXT для примера: |
| 9 1 2 3 4 2 3 5 4 6 5 7 8 9 6 8 9 7 8 9 | 4 1 4 1 3 4 6 1 2 3 5 6 9 5 7 6 8 |