← 返回题目列表

Codeforces · 242/D

D. 争议

中文机器翻译题面 查看原题

Valera 有 n 个计数器,编号从 1 到 n。其中一些是通过电线连接的,每个计数器都有一个特殊的按钮。

最初,所有计数器都包含数字 0。当您按下某个计数器上的按钮时,它的值会增加 1。此外,通过电线直接连接到它的所有计数器中记录的值都会增加一。

Valera和Ignat开始发生争执,争执如下。 Ignat 想到了一个由 n 个整数 a1, a2, ..., an 组成的序列。瓦莱拉应该选择一组不同的计数器,并按每个计数器上的按钮一次(在其他计数器上,按钮不会被按下)。如果之后有一个数字为 i 的计数器,其值为 ai,则 Valera 输掉这场争论,否则他赢得这场争论。

帮助 Valera 确定他需要在哪些计数器上按下按钮才能赢得争议。

输入

第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 105),表示 Valera 拥有的计数器数量以及通过电线连接的计数器对的数量。

以下 m 行中的每一行都包含两个空格分隔的整数 ui 和 vi (1 ≤ ui, vi ≤ n, ui ≠ vi),这意味着编号为 ui 和 vi 的计数器通过电线连接。确保每对连接的计数器在输入中恰好出现一次。

最后一行包含 n 个空格分隔的整数 a1, a2, ..., an (0 ≤ ai ≤ 105),其中 ai 是 Ignat 为第 i 个计数器选择的值。

输出

如果 Valera 无法赢得争议,则在第一行打印 -1。

否则,在第一行打印整数 k (0 ≤ k ≤ n)。在第二行中,打印 k 个不同的空格分隔整数 - 计数器的编号,Valera 应该按任意顺序按下按钮来赢得争论。

如果存在多个答案,您可以打印其中任何一个。

示例

输入 #1

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

输出 #1

2
1 2

输入 #2

4 2
1 2
3 4
0 0 0 0

输出 #2

3
1 3 4