Problem: Leha plays a computer game, where is on each level is given a connected graph with n vertices and m edges. Graph can contain multiple edges, but can not contain self loops. Each vertex has an integer di, which can be equal to 0, 1 or  - 1. To pass the level, he needs to find a «good» subset of edges of the graph or say, that it doesn't exist. Subset is called «good», if by by leaving only edges from this subset in the original graph, we obtain the following: for every vertex i, di = - 1 or it's degree modulo 2 is equal to di. Leha wants to pass the game as soon as possible and ask you to help him. In case of multiple correct answers, print any of them.

Input

The first line contains two integers n, m (1 ≤ n ≤ 3·105, n - 1 ≤ m ≤ 3·105) — number of vertices and edges.

The second line contains n integers d1, d2, ..., dn ( - 1 ≤ di ≤ 1) — numbers on the vertices.

Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ n) — edges. It's guaranteed, that graph in the input is connected.

Output

Print  - 1 in a single line, if solution doesn't exist. Otherwise in the first line k — number of edges in a subset. In the next k lines indexes of edges. Edges are numerated in order as they are given in the input, starting from 1.

Examples

Input

1 0
1


Output

-1


Input

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


Output

0


Input

2 1
1 1
1 2


Output

1
1


Input

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


Output

1
2

Note

In the first sample we have single vertex without edges. It's degree is 0 and we can not get 1.

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        String[] tokens = in.readLine().trim().split(" ");
        int n = Integer.parseInt(tokens[0]);
        int m = Integer.parseInt(tokens[1]);

        int[] d = new int[n];

        tokens = in.readLine().trim().split(" ");
        for(int i = 0; i < n; i++) {
            d[i] = Integer.parseInt(tokens[i]);
        }

        int[][] edges = new int[m][2];

        for(int i = 0; i < m; i++) {
            tokens = in.readLine().trim().split(" ");
            edges[i][0] = Integer.parseInt(tokens[0]) - 1;
            edges[i][1] = Integer.parseInt(tokens[1]) - 1;
        }

        solve(n, m, d, edges);
    }

    public static void solve(int n, int m, int[] d, int[][] edges) {
        PrintWriter out = new PrintWriter(System.out);
        if(subsetSelectionPossible(d)) {
            List<Integer> subsetEdgeNumbers = getGoodSubsetOfEdges(n, m, d, edges);
            out.println(subsetEdgeNumbers.size());
            for(int edgeNumber : subsetEdgeNumbers) {
                out.println(edgeNumber + 1);
            }

        } else {
            out.println(-1);
        }
        out.flush();
        out.close();
    }

    private static boolean subsetSelectionPossible(int[] d) {
        int sumOfDegrees = 0;
        int cntOfMinusOneDegrees = 0;
        for(int i = 0; i < d.length; i++) {
            if(d[i] != -1) {
                sumOfDegrees += d[i];
            } else {
                cntOfMinusOneDegrees++;
            }
        }

        if(sumOfDegrees % 2 == 0) {
            return true;
        }
        return (cntOfMinusOneDegrees >= 1);
    }

    private static List<Integer> getGoodSubsetOfEdges(int n, int m, int[] d, int[][] edges) {
        int[] newDegrees = getAValidSetOfDegreesForVetrices(d);
        int[][] adj = getAdjcencyList(n, m, edges);
        TreeSet<Node> leafNodesOfMST = bfs(0, adj, n, newDegrees);
        List<Integer> subsetEdgeNumbers = new ArrayList<>();

        Map<Long, Integer> edgeNumberMap = new HashMap<>();

        for(int i = 0; i < m; i++) {
            int u = edges[i][0];
            int v = edges[i][1];

            edgeNumberMap.put(getIsEdgeIncludedKey(u, v), i);
            edgeNumberMap.put(getIsEdgeIncludedKey(v, u), i);
        }

        while(!leafNodesOfMST.isEmpty()) {
            Node uNode = leafNodesOfMST.pollFirst();
            Node parentNode = uNode.getParent();

            if(parentNode == null) {
                continue;
            }

            if((uNode.getActualDegree() % 2) != uNode.getExpectedDegree()) {
                // Consider the edge to parent
                int u = uNode.getId();
                int v = parentNode.getId();
                int edgeNumber = edgeNumberMap.get(getIsEdgeIncludedKey(u, v));
                subsetEdgeNumbers.add(edgeNumber);
            } else {
                // Do not consider the edge to parent
                parentNode.setActualDegree(parentNode.getActualDegree() - 1);
            }

            leafNodesOfMST.add(parentNode);
        }

        Collections.sort(subsetEdgeNumbers);
        return subsetEdgeNumbers;
    }

    private static int[] getAValidSetOfDegreesForVetrices(int[] d) {
        int[] newDegrees = new int[d.length];

        int sumOfDegrees = 0;
        int posOfFirstMinusOneDegree = -1;
        for(int i = 0; i < d.length; i++) {
            if(d[i] != -1) {
                newDegrees[i] = d[i];
                sumOfDegrees += d[i];
            } else {
                posOfFirstMinusOneDegree = i;
            }
        }

        if(sumOfDegrees % 2 == 1) {
            newDegrees[posOfFirstMinusOneDegree] = 1;
        }
        return newDegrees;
    }

    private static int[][] getAdjcencyList(int n, int m, int[][] edges) {
        int[][] adj = new int[n][];
        int[] adjSize = new int[n];

        Set<Long> isEdgeIncluded = new HashSet<>();

        for(int i = 0; i < m; i++) {
            int u = edges[i][0];
            int v = edges[i][1];

            if(isEdgeIncluded.contains(getIsEdgeIncludedKey(u, v))) {
                continue;
            }

            adjSize[u]++;
            adjSize[v]++;

            isEdgeIncluded.add(getIsEdgeIncludedKey(u, v));
            isEdgeIncluded.add(getIsEdgeIncludedKey(v, u));
        }

        for(int i = 0; i < n; i++) {
            adj[i] = new int[adjSize[i]];
            adjSize[i] = 0;
        }

        isEdgeIncluded.clear();

        for(int i = 0; i < m; i++) {
            int u = edges[i][0];
            int v = edges[i][1];

            if(isEdgeIncluded.contains(getIsEdgeIncludedKey(u, v))) {
                continue;
            }

            adj[u][adjSize[u]++] = v;
            adj[v][adjSize[v]++] = u;

            isEdgeIncluded.add(getIsEdgeIncludedKey(u, v));
            isEdgeIncluded.add(getIsEdgeIncludedKey(v, u));
        }

        return adj;
    }

    private static long getIsEdgeIncludedKey(int u, int v) {
        long OFFSET = (long) Integer.MAX_VALUE;
        return (u * OFFSET) + v;
    }

    private static TreeSet<Node> bfs(int root, int[][] adj, int n, int[] d) {
        Stack<Node> stack = new Stack<>();
        boolean[] visited = new boolean[n];
        TreeSet<Node> leafNodes = new TreeSet<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if(o1.getDepth() != o2.getDepth()) {
                    return (o2.getDepth() - o1.getDepth());
                } else {
                    return (o1.getId() - o2.getId());
                }
            }
        });

        Node rootNode = new Node(root, d[root], 0);
        stack.push(rootNode);
        visited[root] = true;

        while (!stack.isEmpty()) {
            Node uNode = stack.pop();
            int u = uNode.getId();
            int cntOfSubtreeConnectedEdges = 0;

            for(int i = 0; i < adj[u].length; i++) {
                int v = adj[u][i];

                if(uNode.getParent() != null && uNode.getParent().getId() == v) {
                    continue;
                }

                if(!visited[v]) {
                    Node vNode = new Node(v, d[v], uNode.getDepth() + 1, uNode);
                    stack.add(vNode);
                    visited[v] = true;
                    cntOfSubtreeConnectedEdges++;
                }
            }

            uNode.setActualDegree(cntOfSubtreeConnectedEdges);

            if(cntOfSubtreeConnectedEdges == 0) {
                leafNodes.add(uNode);
            }
        }

        return leafNodes;
    }

    static class Node {
        private int id;
        private int expectedDegree;
        private int actualDegree;
        private int depth;
        private Node parent;

        public Node(int id, int expectedDegree, int depth) {
            this.id = id;
            this.expectedDegree = expectedDegree;
            this.depth = depth;
            this.parent = null;
        }

        public Node(int id, int expectedDegree, int depth, Node parent) {
            this.id = id;
            this.expectedDegree = expectedDegree;
            this.depth = depth;
            this.parent = parent;
        }

        public int getId() {
            return id;
        }

        public int getExpectedDegree() {
            return expectedDegree;
        }

        public void setActualDegree(int actualDegree) {
            this.actualDegree = actualDegree;
        }

        public int getActualDegree() {
            return actualDegree;
        }

        public int getDepth() {
            return depth;
        }

        public Node getParent() {
            return parent;
        }
    }
}