萨莎生活在一个幸福的大家庭。在男人节这一天,家里的所有男人都会按照自己的传统聚集在一起庆祝。萨沙家里有n个男人,所以我们用1到n的整数来编号。
每个男人最多有一个父亲,但可以有任意数量的儿子。
如果至少满足以下条件之一,则 A 号男士被视为 B 号男士的祖先:
- A = B;
- 男号A是男号B的父亲;
- 有一个男人编号C,因此男人编号A是他的祖先,而男人编号C是男人编号B的父亲。
当然,如果男人号A是男人号B的祖先并且A≠B,那么男人号B就不是男人号A的祖先。
Sasha家族的传统是在男人节送礼物。因为以正常方式送礼物很无聊,所以每年都会发生以下情况。
1. 准备一份候选人名单,其中按某种顺序包含 n 名候选人中的一些(可能是全部)。
2. n 个人决定赠送一份礼物。
3. 为了选择一个送礼物的人,男人 A 浏览列表并选择列表中的第一个男人 B,这样 B 就是 A 的祖先并给了他一份礼物。请注意,根据定义,一个人可能会向自己赠送礼物。
4. 如果列表中没有一个人的祖先,他会变得悲伤并离开庆祝活动而不向任何人赠送礼物。
今年你决定帮助组织庆祝活动,并询问n个男人中的每一个,他们想要给谁送礼物(这个人只能从祖先中选择)。你能不能列出一份候选人名单,让他们按照上述流程送礼物就能满足所有愿望?
输入
在输入的第一行中给出了两个整数 n 和 m (0 ≤ m < n ≤ 100 000)——分别是 Sasha 家庭中的男性人数和家庭关系的数量。
接下来的 m 行描述家庭关系:第 (i + 1) 行由一对整数 pi 和 qi (1 ≤ pi, qi ≤ n, pi ≠ qi) 组成,这意味着编号为 pi 的男人是编号为 qi 的男人的父亲。保证每对数字最多出现一次,每对两个不同的人中至少有一个人不是另一个人的祖先,并且每个人至多有一个父亲。
下一行包含n个整数a1, a2, ..., an (1 ≤ ai ≤ n),其中第i个整数表示编号为i的人想要给编号为ai的人送礼物。保证对于每个 1 ≤ i ≤ n,编号为 ai 的人是编号为 i 的人的祖先。
输出
在第一行打印一个整数 k (1 ≤ k ≤ n) — 候选人列表中的男性人数。
然后打印 k 个成对的不超过 n 的不同正整数 — 列表中男人的数量,按照满足每个男人的愿望的顺序,每行一个。
如果有多个合适的列表,请打印其中任何一个。如果没有合适的列表,则在唯一的行中打印 - 1。
示例
输入 #1
3 2 1 2 2 3 1 2 1
输出 #1
-1
输入 #2
4 2 1 2 3 4 1 2 3 3
输出 #2
3 2 1 3
注意
第一个示例解释:
- 如果列表中没有 1,则第一个人和第三个人的愿望将无法满足 (a1 = a3 = 1);
- 如果列表中没有 2,则第二个人的愿望将无法满足 (a2 = 2);
- 如果答案中 1 位于 2 之前,那么第二个人必须将礼物送给第一个人,但他想把礼物送给自己 (a2 = 2)。
- 另一方面,如果编号 2 的人留在编号 1 的人之前,那么第三个人必须将礼物送给第二个人,而不是第一个人 (a3 = 1)。