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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.stream.IntStream;
import java.util.Arrays;
import java.util.Collection;
import java.util.Set;
import java.io.IOException;
import java.util.stream.Collectors;
import java.io.InputStreamReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.stream.Stream;
import java.util.StringTokenizer;
import java.util.Map;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author ShekharN
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.nextInt(), m = in.nextInt();
            Graph graph = new Graph(n, m);
            for (int i = 1; i <= n; i++) {
                graph.getNodeById(i).setValue(in.nextInt());
            }
            List<Integer> ans = new ArrayList<>();
            List<GraphEdge> edges = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                int x = in.nextInt(), y = in.nextInt();
                graph.addEdge(i, x, y);
            }
            int sum1 = (int) Arrays.stream(graph.getVertices()).map(GraphNode::getValue).filter(i -> i == 1).count();
            if ((sum1 & 1) == 1) {
                for (GraphNode graphNode : graph.getVertices()) {
                    if (graphNode.getValue() == -1) {
                        graphNode.setValue(1);
                        break;
                    }
                }
            }
            for (GraphNode graphNode : graph.getVertices()) {
                if (graphNode.getValue() == -1) {
                    graphNode.setValue(0);
                }
            }
            sum1 = (int) Arrays.stream(graph.getVertices()).map(GraphNode::getValue).filter(i -> i == 1).count();
            if ((sum1 & 1) == 1) {
                out.println(-1);
            } else {
                List<GraphEdge> result = new ArrayList<>();
                for (GraphNode graphNode : graph.getVertices()) {
                    dfs(graph, result, graph.getNodeById(1));
                }
                out.println(result.size());
                Map<GraphEdge, Integer> edgeIdMap = graph.getEdges().stream().collect(Collectors.toMap(e -> e, GraphEdge::getId));
                for (GraphEdge graphEdge : result) {
                    out.println(edgeIdMap.get(graphEdge) + 1);
                }
            }
        }

        private void dfs(Graph graph, List<GraphEdge> result, GraphNode cur) {
            if (cur.isNotVisited()) {
                cur.setVisited(true);
                for (GraphNode child : cur.getReachableNodes()) {
                    if (child.isNotVisited()) {
                        dfs(graph, result, child);
                        if (child.getValue() == 1) {
                            result.add(new GraphEdge(child.getId(), cur.getId(), child.getId()));
                            cur.setValue(cur.getValue() ^ 1);
                        }
                    }
                }
            }
        }

    }

    static class Graph {
        private Graph.GraphType type = Graph.GraphType.UNDIRECTED;
        private Set<GraphEdge> edges;
        private GraphNode[] vertices;

        public GraphNode getNodeById(int id) {
            return vertices[id];
        }

        public void addEdge(int id, int srcId, int destId) {
            addEdge(new GraphEdge(id, srcId, destId));
            if (type == Graph.GraphType.UNDIRECTED)
                addEdge(new GraphEdge(id, destId, srcId));
        }

        public void addEdge(GraphEdge e) {
            edges.add(e);
            if (vertices[e.getSrcNode()] == null)
                vertices[e.getSrcNode()] = new GraphNode(e.getSrcNode());
            if (vertices[e.getDestNode()] == null)
                vertices[e.getDestNode()] = new GraphNode(e.getDestNode());
            vertices[e.getSrcNode()].addReachableNode(vertices[e.getDestNode()]);
        }

        public Graph(GraphNode[] vertices, Set<GraphEdge> edges) {
            this(vertices, edges, Graph.GraphType.UNDIRECTED);
        }

        public Graph(int noOfVertices, int noOfEdges) {
            this(noOfVertices, noOfEdges, Graph.GraphType.UNDIRECTED);
        }

        public Graph(int noOfVertices, int noOfEdges, Graph.GraphType type) {
            this(IntStream.rangeClosed(0, noOfVertices).boxed()
                    .map(i -> new GraphNode(i)).toArray(size -> new GraphNode[size]), new HashSet<>(noOfEdges), type);
        }

        public Graph(GraphNode[] vertices, Set<GraphEdge> edges, Graph.GraphType type) {
            this.edges = edges;
            this.vertices = vertices;
            this.type = type;
        }

        public Set<GraphEdge> getEdges() {
            return edges;
        }

        public GraphNode[] getVertices() {
            return vertices;
        }

        public enum GraphType {
            UNDIRECTED,;
        }

    }

    static class GraphNode {
        private int id;
        private List<GraphNode> reachableNodes;
        private int value = 0;
        private boolean visited = false;

        public GraphNode(int id) {
            this(id, new ArrayList<>());
        }

        public GraphNode(int id, List<GraphNode> reachableNodes) {
            this.id = id;
            this.reachableNodes = reachableNodes;
        }

        public int getId() {
            return id;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public List<GraphNode> getReachableNodes() {
            return reachableNodes;
        }

        public void addReachableNode(GraphNode val) {
            this.reachableNodes.add(val);
        }

        public boolean isNotVisited() {
            return !visited;
        }

        public void setVisited(boolean visited) {
            this.visited = visited;
        }


        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            GraphNode graphNode = (GraphNode) o;

            return id == graphNode.id;
        }


        public int hashCode() {
            return id;
        }

    }

    static class FastScanner {
        private BufferedReader br;
        private StringTokenizer st;

        public FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }

        public String nextString() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextString());
        }

    }

    static class GraphEdge {
        private int id;
        private int weight;
        private int srcNode;
        private int destNode;

        public GraphEdge(int id, int weight, int srcNode, int destNode) {
            this.id = id;
            this.weight = weight;
            this.srcNode = srcNode;
            this.destNode = destNode;
        }

        public GraphEdge(int id, int srcNode, int destNode) {
            this.id = id;
            this.srcNode = srcNode;
            this.destNode = destNode;
            this.weight = 1;
        }

        public int getId() {
            return id;
        }

        public int getSrcNode() {
            return srcNode;
        }

        public int getDestNode() {
            return destNode;
        }


        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            GraphEdge graphEdge = (GraphEdge) o;

            //if (id != graphEdge.id) return false;
            if (weight != graphEdge.weight) return false;
            if (srcNode != graphEdge.srcNode) return false;
            return destNode == graphEdge.destNode;
        }


        public int hashCode() {
            int result = weight;
            //result = 31 * result + weight;
            result = 31 * result + srcNode;
            result = 31 * result + destNode;
            return result;
        }

    }
}