В одном королевстве n городов и m дорог. У каждого города есть своё название, состоящее из строчных латинских букв. Но королю не нравится, что есть дороги, ведущие из города с названием, являющимся лексикографически меньшим названия конечного. Он захотел это исправить, поменяв города, к которым относятся те или иные названия. Сам он, конечно, не справится. Помогите ему в этом!
Формат файла входных данных:
Первая строка содержит два целых числа n и m (2 <= n <= 1000; 1 <= M <= 10000) - количество городов и дорог в королевстве соответственно.
Вторая строка содержит n строк, описывающих города. Описание задаётся строкой из строчных латинских букв - названия города.
Далее в m строках перечислены дороги. Каждая дорога задаётся парой чисел - номерами начального и конечного городов соответственно. Дороги односторонние.
Формат файла выходных данных:
Вывести n чисел, каждое из которых обозначает номер названия, соответствующего i-ому городу. Если решения не существует, вывести -1.
| Ввод |
Вывод |
|
4 4
aaa bacc cqe de
1 4
4 2
4 3
3 2
|
1 4 3 2 |
|
3 3
fi bru a
1 2
2 3
3 1
|
-1 |
(с) Филимонов И.