После получения разноцветного диплома об окончании факультета Высокой Магии и Колдовства Марсианского Галактического Университета, Пафнутий готовится поступать в аспирантуру. На лето он устроился системным администратором в контору по заготовке чистых стёкол и прямых досок, рассчитывая, что работа почти не будет отвлекать его от подготовки к вступительным экзаменам. Но вместо ожидаемого погружения в мир прикладной магии (и сапёра) Пафнутию каждый день приходится сталкиваться со сложными задачами!

В компании работает N сотрудников, каждый из которых использует ровно один персональный компьютер. Машины объединены в сеть с помощью N - 1 соединений, разрешающих парам компьютеров обмениваться данными в любом направлении. Сеть спроектирована таким образом, что между любой парой компьютеров существует ровно один кратчайший (по числу соединений) путь.

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

Сообщения передаются при помощи интерфейса, который ещё помнит, как весело жужжала старушка БЭСМ-6. Его работа происходит строго по следующим правилам:

1. На каждой машине имеется ячейка памяти, в которой в любой момент времени может находиться не более одного сообщения.
2. Пока сеть выключена, любой сотрудник может создать сообщение для отправки коллегам. Для этого он помещает сообщение в ячейку памяти своего компьютера и задаёт список адресатов. Как только сеть активируется, возможность создания сообщений отключается и начинается их пересылка.
3. Пересылка состоит из последовательного выполнения операций передачи сообщения от одного компьютера, на котором создано сообщение, к другому, который находится в списке адресатов. Определение порядка передачи всех сообщений и есть основная функция системного администратора в данном учреждении.
4. В процессе передачи сообщения между компьютерами v и u оно обязательно будет записано в ячейки памяти всех компьютеров, расположенных на кратчайшем пути между v и u.
5. Если после выполнения очередной операции пересылки все исходные сообщения находятся в ячейках памяти всех своих адресатов, то работа интерфейса передачи сообщений считается успешно выполненной и сеть снова выключается. Что находится в этот момент в ячейках памяти компьютеров, которым не было адресовано ни одного сообщения, не имеет значения.

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

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