今天约翰尼想要增加他的贡献。他的计划假设撰写 $$$n$$$ 博客。一个博客涵盖一个主题,但多个博客可以涵盖一个主题。此外,一些博客之间还存在相互引用。通过参考连接的每对博客必须涵盖不同的主题,否则读者会注意到它们只是为了更多的贡献而分开的。博客的集合以及其中一些对之间的双向引用称为博客网络。
有 $$$n$$$ 个不同的主题,编号从 $$$1$$$ 到 $$$n$$$,按 Johnny 的知识排序。博客网络的结构已经准备好了。现在约翰尼必须按某种顺序写博客。他很懒,所以每次写博客之前,他都会看看已经写过的邻居(引用当前博客的博客),然后选择没有被邻居覆盖的数量最小的主题。很容易看出,这个策略总是允许他选择一个主题,因为最多有 $$$n - 1$$$ 邻居。
例如,如果当前博客的已写入邻居的主题编号为 $$$1$$$、$$$3$$$、$$$1$$$、$$$5$$$ 和 $$$2$$$,Johnny 将为当前博客选择主题编号 $$$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$$$ 表示第 $$$i$$$ 博客的所需主题号 ($$$1 \le t_i \le n$$$)。
输出
如果解不存在,则写$$$-1$$$。否则,输出 $$$n$$$ 不同的整数 $$$p_1, p_2, \ldots, p_n$$$ $$$(1 \leq p_i \leq n)$$$,它们按照 Johnny 应该写的顺序描述博客的数量。如果有多个答案,请打印其中一个。
示例
输入 #1
3 3 1 2 2 3 3 1 2 1 3
输出 #1
2 1 3
输入 #2
3 3 1 2 2 3 3 1 1 1 1
输出 #2
-1
输入 #3
5 3 1 2 2 3 4 5 2 1 2 2 1
输出 #3
2 5 1 3 4
注意
在第一个示例中,Johnny 从写入博客编号 $$$2$$$ 开始,还没有已写入的邻居,因此它接收第一个主题。后来他写了博客号$$$1$$$,它引用了已经写的第二篇博客,所以它收到了第二个主题。最后,他写了博客编号 $$$3$$$,它引用了博客编号 $$$1$$$ 和 $$$2$$$,因此它收到了第三个主题。
第二个例子:不存在满足给定条件的任何排列。
第三个例子:第一个 Johnny 写博客 $$$2$$$,它收到主题 $$$1$$$。然后他写博客$$$5$$$,它也收到主题$$$1$$$,因为它没有引用单个已写的博客$$$2$$$。然后他写入博客编号$$$1$$$,它引用了主题为$$$1$$$的博客编号$$$2$$$,因此它接收到主题$$$2$$$。然后他写入博客编号$$$3$$$,该博客编号引用了博客$$$2$$$,因此它接收主题$$$2$$$。然后他以写博客编号 $$$4$$$ 结束,该博客引用了博客 $$$5$$$ 并接收主题 $$$2$$$。