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。