Gifts by the List

题意翻译

$Sasha$ 生活在一个幸福的大家庭里。在男人节这一天，全家人会按照自己的传统聚会、庆祝。 $Sasha$ 一家有 $n$ 个男人，所以我们用 $1$ 到 $n$ 的整数来给他们编号。 每个人最多有一个父亲，但可以有任意个儿子。 如果满足以下条件中至少一项，则将 $A$ 视为 $B$ 的祖先： - $ A = B $； - $A$ 号人是 $B$ 号人的父亲; - 有一个人 $C$ ，$A$ 是他的祖先，并且 $C$ 是 $B$ 的父亲。 当然，如果 $A$ 是 $B$ 的祖先，并且 $A \neq B$ ，则 $B$ 不是 $A$ 的祖先。 $\Longleftarrow$ ~~（废话请忽略~~ $Sasha$ 一家的传统是在男人节那天送礼物。 由于以正常方式赠送礼物很无聊，因此每年都会发生以下情况： - 有一份候选人名单，以某种顺序包含了一些（**可能全部**）男子。 - $n$ 个男人中的每个都决定送礼物。 - 为了选择要送礼物的人，男人 $A$ 浏览列表，从列表中选择第一个 $A$ 的祖先 $B$ ，并给他礼物。**请注意，根据定义，一个人可能会给自己一份礼物。** - 如果列表中没有某一个人的祖先，那么那个人会难过地离开庆典。**作为报复，他不会给任何人礼物。** 今年，您已决定帮助 $Sasha$ 一家庆祝活动，并询问了那 $n$ 位男士，他们想将礼物送给谁（此被选中者只可能在其祖先中）。 您是否能够列出候选人列表，以便仅按照上述流程送出礼物就可以使所有人都不会伤心？

题目描述

Sasha lives in a big happy family. At the Man's Day all the men of the family gather to celebrate it following their own traditions. There are $ n $ men in Sasha's family, so let's number them with integers from $ 1 $ to $ n $ . Each man has at most one father but may have arbitrary number of sons. Man number $ A $ is considered to be the ancestor of the man number $ B $ if at least one of the following conditions is satisfied: - $ A=B $ ; - the man number $ A $ is the father of the man number $ B $ ; - there is a man number $ C $ , such that the man number $ A $ is his ancestor and the man number $ C $ is the father of the man number $ B $ . Of course, if the man number $ A $ is an ancestor of the man number $ B $ and $ A≠B $ , then the man number $ B $ is not an ancestor of the man number $ A $ . The tradition of the Sasha's family is to give gifts at the Man's Day. Because giving gifts in a normal way is boring, each year the following happens. 1. A list of candidates is prepared, containing some (possibly all) of the $ n $ men in some order. 2. Each of the $ n $ men decides to give a gift. 3. In order to choose a person to give a gift to, man $ A $ looks through the list and picks the first man $ B $ in the list, such that $ B $ is an ancestor of $ A $ and gives him a gift. Note that according to definition it may happen that a person gives a gift to himself. 4. If there is no ancestor of a person in the list, he becomes sad and leaves the celebration without giving a gift to anyone. This year you have decided to help in organizing celebration and asked each of the $ n $ men, who do they want to give presents to (this person is chosen only among ancestors). Are you able to make a list of candidates, such that all the wishes will be satisfied if they give gifts according to the process described above?

输入输出格式

输入格式

In the first line of the input two integers $ n $ and $ m $ ( $ 0<=m&lt;n<=100000 $ ) are given — the number of the men in the Sasha's family and the number of family relations in it respectively. The next $ m $ lines describe family relations: the $ (i+1)^{th} $ line consists of pair of integers $ p_{i} $ and $ q_{i} $ ( $ 1<=p_{i},q_{i}<=n $ , $ p_{i}≠q_{i} $ ) meaning that the man numbered $ p_{i} $ is the father of the man numbered $ q_{i} $ . It is guaranteed that every pair of numbers appears at most once, that among every pair of two different men at least one of them is not an ancestor of another and that every man has at most one father. The next line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=n $ ), $ i^{th} $ of which means that the man numbered $ i $ wants to give a gift to the man numbered $ a_{i} $ . It is guaranteed that for every $ 1<=i<=n $ the man numbered $ a_{i} $ is an ancestor of the man numbered $ i $ .

输出格式

Print an integer $ k $ $ (1<=k<=n) $ — the number of the men in the list of candidates, in the first line. Print then $ k $ pairwise different positive integers not exceeding $ n $ — the numbers of the men in the list in an order satisfying every of the men's wishes, one per line. If there are more than one appropriate lists, print any of them. If there is no appropriate list print $ -1 $ in the only line.

输入输出样例

输入样例 #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

说明

The first sample explanation: - if there would be no $ 1 $ in the list then the first and the third man's wishes would not be satisfied $ (a_{1}=a_{3}=1) $ ; - if there would be no $ 2 $ in the list then the second man wish would not be satisfied $ (a_{2}=2) $ ; - if $ 1 $ would stay before $ 2 $ in the answer then the second man would have to give his gift to the first man, but he wants to give it to himself $ (a_{2}=2) $ . - if, at the other hand, the man numbered $ 2 $ would stay before the man numbered $ 1 $ , then the third man would have to give his gift to the second man, but not to the first $ (a_{3}=1) $ .

题意翻译

$Sasha$ 生活在一个幸福的大家庭里。在男人节这一天，全家人会按照自己的传统聚会、庆祝。 $Sasha$ 一家有 $n$ 个男人，所以我们用 $1$ 到 $n$ 的整数来给他们编号。 每个人最多有一个父亲，但可以有任意个儿子。 如果满足以下条件中至少一项，则将 $A$ 视为 $B$ 的祖先： - $ A = B $； - $A$ 号人是 $B$ 号人的父亲; - 有一个人 $C$ ，$A$ 是他的祖先，并且 $C$ 是 $B$ 的父亲。 当然，如果 $A$ 是 $B$ 的祖先，并且 $A \neq B$ ，则 $B$ 不是 $A$ 的祖先。 $\Longleftarrow$ ~~（废话请忽略~~ $Sasha$ 一家的传统是在男人节那天送礼物。 由于以正常方式赠送礼物很无聊，因此每年都会发生以下情况： - 有一份候选人名单，以某种顺序包含了一些（**可能全部**）男子。 - $n$ 个男人中的每个都决定送礼物。 - 为了选择要送礼物的人，男人 $A$ 浏览列表，从列表中选择第一个 $A$ 的祖先 $B$ ，并给他礼物。**请注意，根据定义，一个人可能会给自己一份礼物。** - 如果列表中没有某一个人的祖先，那么那个人会难过地离开庆典。**作为报复，他不会给任何人礼物。** 今年，您已决定帮助 $Sasha$ 一家庆祝活动，并询问了那 $n$ 位男士，他们想将礼物送给谁（此被选中者只可能在其祖先中）。 您是否能够列出候选人列表，以便仅按照上述流程送出礼物就可以使所有人都不会伤心？