CF681D Gifts by the List

Sasha 生活在一个幸福美满的大家庭。在男子日这天，家族中所有男性成员都会聚在一起，用他们自己的传统庆祝。Sasha 的家族共有 $n$ 名男性，我们可以用 $1$ 到 $n$ 的整数对他们进行编号。 每个人至多有一位父亲，但可以有任意数量的儿子。 如果满足以下至少一个条件，则编号为 $A$ 的男性被视为编号为 $B$ 的男性的祖先： - $A = B$； - 编号为 $A$ 的男性是编号为 $B$ 的男性的父亲； - 存在编号为 $C$ 的男性，使得编号为 $A$ 的男性是编号为 $C$ 的祖先，且编号为 $C$ 的男性是编号为 $B$ 的父亲。 当然，如果编号为 $A$ 的男性是编号为 $B$ 的男性的祖先且 $A \neq B$，那么编号为 $B$ 的男性就不是编号为 $A$ 的男性的祖先。 Sasha 家族的传统是在男子日互赠礼物。因为以普通的方式赠送礼物太过无聊，所以每年都会按以下流程赠送礼物： 1. 准备一个候选人名单，名单中包含一部分（也可能是全部）$n$ 名男性，并有一定的顺序。 2. 每位男性都决定要赠送礼物。 3. 选择赠送礼物的人时，编号为 $A$ 的男性会遍历名单，选择列表中第一个是自己祖先的男性 $B$，并将礼物送给他。注意，按照定义，一个人可能会把礼物送给自己。 4. 如果某人没有在名单中找到自己的祖先，他会伤心地离开庆典，不向任何人送礼。 今年你打算帮助大家组织庆典，并已经询问每一位男性——他想要把礼物送给哪位祖先（只能从祖先中选择）。你能否制作一个候选人名单，使所有人的这一愿望都能按照上述方式实现？

输入第一行包含两个整数 $n$ 和 $m$（$0 \leq m < n \leq 100000$），分别表示 Sasha 家族男性成员的人数和家族关系的数量。 接下来的 $m$ 行描述家族关系：第 $(i+1)$ 行包含两个整数 $p_i$ 和 $q_i$（$1 \leq p_i, q_i \leq n$，$p_i \neq q_i$），表示编号为 $p_i$ 的男性是编号为 $q_i$ 的男性的父亲。保证每对数字最多只出现一次，对于任意两位不同的男性，至少有一位不是另一位的祖先，并且每个人至多只有一位父亲。 接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$），第 $i$ 个数表示编号为 $i$ 的男性想要把礼物送给编号为 $a_i$ 的男性。保证对每个 $1 \leq i \leq n$，编号为 $a_i$ 的男性一定是编号为 $i$ 的男性的祖先。

第一行输出一个整数 $k$（$1 \leq k \leq n$）——候选人名单中的人数。 接下来 $k$ 行，每行输出一个不超过 $n$ 的正整数，表示名单中的男性编号，按满足所有人愿望的顺序排列。 如果有多个符合要求的名单，输出任意一个。如果不存在这样的名单，输出 $-1$。

第一个样例的解释： - 如果名单中不包含 $1$，那么第一个和第三个男性的愿望都无法实现（$a_1 = a_3 = 1$）； - 如果名单中不包含 $2$，那么第二位男性的愿望无法实现（$a_2 = 2$）； - 如果 $1$ 在名单中排列在 $2$ 前面，那么第二个人会不得不给第一个人送礼，但他实际上想把礼物送给自己（$a_2 = 2$）。 - 反之，如果 $2$ 在名单中排列在 $1$ 前面，那么第三个人会不得不给第二个人送礼，而不是第一个人（$a_3 = 1$）。 由 ChatGPT 5 翻译