Сегодня Джонни хочет увеличить свой вклад. Его план подразумевает написание $$$n$$$ блогов. Один блог покрывает одну тему, но одна тема может быть покрыта несколькими блогами. Также, некоторые блоги связаны друг с другом ссылками. Каждая пара блогов, связанных ссылкой, должна покрывать две разные темы. Потому что иначе читатели могут заметить, что блоги разделены только для того, чтобы набрать больше вклада. Множество блогов и двусторонние ссылки между некоторыми парами из них называются сетью блогов.
Всего есть $$$n$$$ различных тем, пронумерованных от $$$1$$$ до $$$n$$$, упорядоченных по пониманию Джонни. Структура сети блогов уже приготовлена. Теперь Джонни должен написать все блоги в некотором порядке. Он ленивый, поэтому каждый раз перед написанием блога, он смотрит на все уже написанные соседние блоги (связанные ссылкой с текущим) и выбирает тему с минимальным номером, которая еще не покрыта соседними блогами. Можно заметить, что такая стратегия всегда позволит ему выбрать тему, потому что максимальное количество соседних блогов равно $$$n - 1$$$.
Например, если уже написанные, соседние с текущим, блоги покрывают темы с номерами $$$1$$$, $$$3$$$, $$$1$$$, $$$5$$$ и $$$2$$$, Джонни выберет тему номер $$$4$$$ для текущего блога, потому что темы номер $$$1$$$, $$$2$$$ и $$$3$$$ уже покрыты соседними блогами, а тема номер $$$4$$$ — нет.
Как хороший друг, вы провели некоторые исследования и предсказали наилучшую темы для каждого блога. Не могли бы вы сказать Джонни, в каком порядке он должен писать блоги, чтобы в результате его стратегии каждый блог покрывал выбранную вами тему?
Первая строка содержит два целых числа $$$n$$$ $$$(1 \leq n \leq 5 \cdot 10^5)$$$ и $$$m$$$ $$$(0 \leq m \leq 5 \cdot 10^5)$$$ — количество блогов и ссылок, соответственно.
Каждая из следующих $$$m$$$ строк содержит два целых числа $$$a$$$ и $$$b$$$ ($$$a \neq b$$$; $$$1 \leq a, b \leq n$$$), которые означают, что в сети блогов есть ссылка между блогами с номерами $$$a$$$ и $$$b$$$. Гарантируется, что граф сети блогов не содержит кратных ребер.
Последняя строка содержит $$$n$$$ целых чисел $$$t_1, t_2, \ldots, t_n$$$, $$$i$$$-е из них обозначает желаемую тему для $$$i$$$-го блога ($$$1 \le t_i \le n$$$).
Если решение не существует, выведите $$$-1$$$. Иначе, выведите $$$n$$$ различных целых чисел $$$p_1, p_2, \ldots, p_n$$$ $$$(1 \leq p_i \leq n)$$$, которые обозначают номера блогов в том порядке, в котором Джонни должен их написать. Если существует несколько решений, выведите любое.
3 3 1 2 2 3 3 1 2 1 3
2 1 3
3 3 1 2 2 3 3 1 1 1 1
-1
5 3 1 2 2 3 4 5 2 1 2 2 1
2 5 1 3 4
В первом примере, Джонни начинает с написания блога номер $$$2$$$, у него пока еще нет написанных соседних блогов, поэтому Джонни выбирает тему номер один. Потом он пишет блог номер $$$1$$$, у него есть ссылка на уже написанный второй блог, поэтому Джонни выбирает вторую тему. Наконец, он пишет блог номер $$$3$$$, у него есть ссылки на блоги номер $$$1$$$ и $$$2$$$, поэтому Джонни выбирает третью тему.
Второй пример: Не существует ни одной перестановки, удовлетворяющей всем условиям.
Третий пример: Сначала Джонни пишет блог номер $$$2$$$, который получает тему $$$1$$$. Затем, он пишет блог $$$5$$$, который тоже получает тему $$$1$$$, потому из него нет ссылки на единственный уже написанный блог (номер $$$2$$$). Затем, он пишет блог $$$1$$$, он получает тему $$$2$$$, потому что из него есть ссылка на блог $$$2$$$ с темой $$$1$$$. Затем, он пишет блог $$$3$$$, из него есть ссылка на блог $$$2$$$, поэтому он получает тему $$$2$$$. Наконец, он пишет блог $$$4$$$, из него есть ссылка на блог $$$5$$$, поэтому он получает тему $$$2$$$.
