← 返回题目列表

Codeforces · 840/B

B. Leha 和另一个关于图表的游戏

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

Leha 玩一个电脑游戏,其中每个级别都有一个具有 n 个顶点和 m 个边的连通图。图可以包含多条边,但不能包含自环。每个顶点都有一个整数 di,它可以等于 0、1 或 - 1。要通过关卡,他需要找到图的边的“好”子集,或者说它不存在。子集被称为“好”,如果通过在原始图中仅保留该子集的边,我们得到以下结果:对于每个顶点 i,di = - 1 或者它的度模 2 等于 di。 Leha想尽快通过游戏并请你帮助他。如果有多个正确答案,请打印其中任何一个。

输入

第一行包含两个整数 n, m (1 ≤ n ≤ 3·105, n - 1 ≤ m ≤ 3·105) — 顶点和边的数量。

第二行包含 n 个整数 d1, d2, ..., dn (- 1 ≤ di ≤ 1) — 顶点上的数字。

接下来的 m 行中的每一行都包含两个整数 u 和 v (1 ≤ u, v ≤ n) — 边。可以保证输入中的图形是连通的。

输出

如果解不存在,则在一行中打印 - 1。否则在第一行 k — 子集中的边数。在接下来的 k 行中,边的索引。边按照输入中给出的顺序从 1 开始编号。

示例

输入 #1

1 0
1

输出 #1

-1

输入 #2

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

输出 #2

0

输入 #3

2 1
1 1
1 2

输出 #3

1
1

输入#4

3 3
0 -1 1
1 2
2 3
1 3

输出#4

1
2

注意

在第一个示例中,我们有没有边的单个顶点。它的度数是0,我们不能得到1。