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.util.*;
import java.io.*;

/**
 *
 * @author rohan
 */

public class Main {

    static int mod = (int) (1e9+7);
    static int N   = (int)3e5+20;
    static ArrayList<Integer>[] al ;
    static ArrayList<Integer> ans;
    static int[][] eg;
    static int[] t;
    static boolean[] vis;
    static int n , m, st;

    static void solve(){
        

        al  = new ArrayList[N];
        ans = new ArrayList<Integer>();
        eg  = new int[N][2];
        t   = new int[N];
        vis = new boolean[N];

        for(int i=0;i<N;i++)
        {
            al[i] = new ArrayList<Integer>();
        }

        n = sc.nextInt();
        m = sc.nextInt();
        st = -1;
        int flag = 0;
        for(int i=0;i<n;i++)
        {
            t[i] = sc.nextInt();
            if(t[i] == -1 && flag==0)
            {
                 st = i;
                 flag = 1;
            }   
        }

        for(int i=0;i<m;i++)
        {
            int x = sc.nextInt()-1;
            int y = sc.nextInt()-1;
            eg[i][0] = x; eg[i][1] =y;

            al[x].add(i);
            al[y].add(i);
        }

        if(st == -1)
        {
            int x = dfs(0);
            if(x==-1)
            {
                out.println(-1);
                out.flush();
                return;
            }
        }
        else
        {
            dfs(st);
        }
        out.println(ans.size());
        for(Integer e : ans)
        {
            out.println(e);
        }
        out.close();
    }
    static int dfs(int v)
    {
        vis[v] = true;
        int c = 0;
        for(Integer i: al[v])
        {
            int u = eg[i][0] + eg[i][1] - v;
            if(vis[u] == true) continue;
            int x = dfs(u);
            if(x==-1)
            {
                c++;
                ans.add(i+1);
            }
        }
        if(t[v]==-1 || (t[v] == (c%2)))    return 1;
        return -1;
    }
    //////////////////////////////////////////////////////////////////////////////////////
    
////////////////////////////////////////////////////////////////////////////////////////////////////////////////   
    static InputReader sc = new InputReader(System.in);
    static PrintWriter out = new PrintWriter(System.out); 
    public static void main(String[] args) {
        
        new Thread(null ,new Runnable(){

            public void run(){
                try{
                    solve();
                } catch(Exception e){
                    e.printStackTrace();
                }
            }
        },"1",1<<26).start();
        
    }
    
    static class Pair implements Comparable<Pair>{

        long x,y;
        long c,k;
        
        Pair (int x,int y,long c){
            this.x=x;
            this.y=y;
            this.c=c;
        }

        Pair (long x,long y){
            this.x=x;
            this.y=y;
        }
        
        public int compareTo(Pair o) {
               return Long.compare(this.x,o.x);
        //return 0;
        }

        public boolean equals(Object o) {
            if (o instanceof Pair) 
            {
                Pair p = (Pair)o;
                return p.x == x && p.y == y;
            }
            return false;
        }

        @Override
        public String toString() {
            return x+" "+y+" "+c+" "+k;
        }
        
    } 
    public static class Merge {
        
        public static void sort(int inputArr[]) {
            int length = inputArr.length;
            doMergeSort(inputArr,0, length - 1);
        }
        
        private static void doMergeSort(int[] arr,int lowerIndex, int higherIndex) {        
            if (lowerIndex < higherIndex) {
                int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
                doMergeSort(arr,lowerIndex, middle);
                doMergeSort(arr,middle + 1, higherIndex);
                mergeParts(arr,lowerIndex, middle, higherIndex);
            }
        }
        
        private static void mergeParts(int[]array,int lowerIndex, int middle, int higherIndex) {
            int[] temp=new int[higherIndex-lowerIndex+1];
            for (int i = lowerIndex; i <= higherIndex; i++) {
                temp[i-lowerIndex] = array[i];
            }
            int i = lowerIndex;
            int j = middle + 1;
            int k = lowerIndex;
            while (i <= middle && j <= higherIndex) {
                if (temp[i-lowerIndex] < temp[j-lowerIndex]) {
                    array[k] = temp[i-lowerIndex];
                    i++;
                } else {
                    array[k] = temp[j-lowerIndex];
                    j++;
                }
                k++;
            }
            while (i <= middle) {
                array[k] = temp[i-lowerIndex];
                k++;
                i++;
            }
            while(j<=higherIndex){
                array[k]=temp[j-lowerIndex];
                k++;
                j++;
            }
        }

    }
    
    static long[] shuffle(long[] a, Random gen){ 
        for(int i = 0, n = a.length;i < n;i++){ 
            int ind = gen.nextInt(n-i)+i; 
            long d = a[i]; 
            a[i] = a[ind]; 
            a[ind] = d; 
        } 
        return a; 
    }

        
    public static long add(long a,long b){
        long x=(a+b);
        while(x>=mod) x-=mod;
        return x;
    }

    public static long sub(long a,long b){
        long x=(a-b);
        while(x<0) x+=mod;
        return x;
    }
    
    public static long mul(long a,long b){
        a%=mod;
        b%=mod;
        long x=(a*b);
        return x%mod;
    }
    
    static boolean isPal(String s){
        for(int i=0, j=s.length()-1;i<=j;i++,j--){
                if(s.charAt(i)!=s.charAt(j)) return false;
        }
        return true;
    }
    static String rev(String s){
            StringBuilder sb=new StringBuilder(s);
            sb.reverse();
            return sb.toString();
    }

    static long gcd(long x,long y){
    if(y==0)
        return x;
    else
        return gcd(y,x%y);
    }
    
    static int gcd(int x,int y){
    if(y==0)
        return x;
    else 
        return gcd(y,x%y);
    }

    static long gcdExtended(long a,long b,long[] x){

        if(a==0){
            x[0]=0;
            x[1]=1;
            return b;
        }
        long[] y=new long[2];
        long gcd=gcdExtended(b%a, a, y);

        x[0]=y[1]-(b/a)*y[0];
        x[1]=y[0];

        return gcd;
    }

    static int abs(int a,int b){
        return (int)Math.abs(a-b);
    }

    static long abs(long a,long b){
        return (long)Math.abs(a-b);
    }

    static int max(int a,int b){
        if(a>b)
            return a;
        else
            return b;
    }

    static int min(int a,int b){
        if(a>b)
            return b;
        else 
            return a;
    }

    static long max(long a,long b){
        if(a>b)
            return a;
        else
            return b;
    }

    static long min(long a,long b){
        if(a>b)
            return b;
        else 
            return a;
    }


    public static long pow(long n,long p,long m){
        long  result = 1;
        if(p==0)
            return 1;
          
        while(p!=0)
        {
            if(p%2==1)
                 result *= n;
            if(result>=m)
                 result%=m;
            p >>=1;
            n*=n;
            if(n>=m)
            n%=m;
        }
        return result;
    }
    
    public static long pow(long n,long p){
        long  result = 1;
        if(p==0)
            return 1;
          
        while(p!=0)
        {
            if(p%2==1)
                result *= n;        
            p >>=1;
            n*=n;       
        }
        return result;
    }
    
    static void debug(Object... o) {
            System.out.println(Arrays.deepToString(o));
    }

    static class InputReader{
        final InputStream stream;
        final byte[] buf = new byte[8192];
        int curChar, numChars;
        SpaceCharFilter filter;
 
        public InputReader(InputStream stream){
            this.stream = stream;
        }
 
        public int read(){
            if(numChars == -1){
                throw new InputMismatchException();
            }
            if(curChar >= numChars){
                curChar = 0;
                try{
                    numChars = stream.read(buf);
                } catch(IOException e){
                    throw new InputMismatchException();
                }
                if(numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
 
        public int nextInt(){
            int c = read();
            while(isSpaceChar(c))
                c = read();
            int sgn = 1;
            if(c == '-'){
                sgn = -1;
                c = read();
            }
            int res = 0;
            do{
                if(c<'0' || c>'9'){
                    throw new InputMismatchException();}
                res *= 10;
                res += c - '0';
                c = read();
            } while(!isSpaceChar(c));
            return res*sgn;
        }
 
        public long nextLong(){
            int c = read();
            while(isSpaceChar(c))
                c = read();
            int sgn = 1;
            if(c == '-'){
                sgn = -1;
                c = read();
            }
            long res = 0;
            do{
                if(c<'0' || c>'9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while(!isSpaceChar(c));
            return res*sgn;
        }
 
        public String next(){
            int c = read();
            while(isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do{
                res.appendCodePoint(c);
                c = read();
            }while(!isSpaceChar(c));
            return res.toString();
        }
 
        public boolean isSpaceChar(int c){
            if(filter != null)
                return filter.isSpaceChar(c);
            return c==' ' || c=='\n' || c=='\r' || c=='\t' || c==-1;
        }
 
        public interface SpaceCharFilter{
            public boolean isSpaceChar(int ch);
        }
    }
}