#62. 「2023 新疆省赛」任务安排

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: woruo

题目描述

又到了忙碌的星期一。沃若打开飞书,发现有 个任务需要完成。为了方便起见,沃若对任务从 进行编号。

他每次会选择一个任务,做完当前任务以后才会开始选择下一个任务去完成。

但这些任务可不是随便想做哪个就可以做哪个的。具体来说,任务之间有 对依赖关系 ,表示在做编号为 的任务之前,必须先完成编号为 的任务。

特别地,还有一个长度为 的序列 ,表示 个指定任务的编号,沃若需要保证这 个指定任务是连续完成的。即:如果某一时刻他选择了去完成编号为 的任务,那接下来他就只能依次完成编号为 的任务。在编号为 的任务完成后,他才能选择序列 之外的其他任务去完成。

请你帮沃若找出一种完成任务的顺序,满足以上的所有限制。

输入格式

输入的第一行为两个空格分隔的正整数 ,分别表示任务和依赖关系的数量。

随后 行,每行两个空格分隔的正整数 ,表示一对依赖关系。保证输入中不存在两对完全相同的依赖关系,即有序二元组 两两不同。

接下来一行一个正整数 ,表示序列 的长度。

随后一行 个空格分隔的正整数 ,表示序列 ,含义如题目描述中所示。保证输入的序列 中的数字两两不同。

输出格式

输出一行 个空格分隔的正整数,表示完成任务的顺序。

如果有多个满足条件的解,你可以输出任意一个。

如果无解,则输出一行一个整数

样例

样例输入 1

4 4
2 4
1 2
3 4
1 3
2
2 4

样例输出 1

1 3 2 4

样例输入 2

4 5
2 4
1 2
3 4
1 3
2 3
2
2 4

样例输出 2

-1