Города и дороги
(Время: 1 сек. Память: 64 Мб Сложность: 72%)
Известно, что в Байтландии всего N городов и нет дорог! Известно, что все города расположены в различных точках на плоскости и никакие три из них не лежат на одной прямой.
Было решено построить в стране сеть дорог так, чтобы была возможность добраться по дорогам из любого города в любой единственным образом. Каждая дорога представляет собой отрезок, соединяющий некоторую пару городов.
Был подготовлен проект, включающий описание из N-1 непересекающихся дорог. Каждая дорога задаётся парой городов и в целях секретности вместо названий городов были использованы коды – числа от 1 до N.
Однако документ, содержащий соответствие кодов городам, был утерян. Была поставлена задача: найти хоть какое-то возможное сопоставление номеров городам. К сожалению, из-за того, что пересечение дорог недопустимо, не любой вариант подходит. Это значительно усложнило задачу.
Вам требуется сопоставить числам от 1 до N города так, чтобы после реализации проекта не было пересечений дорог вне городов, которые их соединяют.
Входные данные
В первой строке входного файла INPUT.TXT содержится целое число N – количество городов в Байтландии (2 ≤ N ≤ 1500).
Далее следует N описаний городов. Описание каждого города состоит из двух строк. Первая строка содержит название города – строку, состоящую из символов с ASCII-кодами от 33 до 127. Названия различных городов не совпадают. Названия городов имеют длину от 1 до 60 символов. Вторая строка описания города содержит два целых числа x и y – координаты города. Координаты не превышают 104 по абсолютной величине. Гарантируется, что никакие три города не лежат на одной прямой.
Далее следуют N-1 строк, которые описывают проект постройки сети дорог в его текущем состоянии. Каждая строка содержит по два целых числа от 1 до N – номера городов, соединённых дорогой в проекте. Никакая дорога в проекте не соединяет город сам с собой, никакие два города не соединены более чем одной дорогой. В проекте упомянуты все города от 1 до N. По дорогам проекта можно добраться от любого города до любого другого.
Выходные данные
В выходной файл OUTPUT.TXT выведите N строк, i-я из этих строк должна содержать название города, который следует сопоставить числу i в проекте. Если решений несколько, выведите любое.
Если решения не существует, выведите «No solution».
Пример
№ | INPUT.TXT | OUTPUT.TXT | Пояснение |
1 | 6
Borodino
2 -1
Achinsk
-3 1
Abakan
-2 -4
Lesosibirsk
-1 4
Kansk
3 1
Krasnoyarsk
0 0
3 5
1 4
4 2
3 4
4 6 | Kansk
Abakan
Achinsk
Krasnoyarsk
Lesosibirsk
Borodino |  |
Система оценки
Решения, работающие только для N ≤ 10, будут оцениваться в 50 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|