Untitled

/*
Created by chris144 on 10/22/2025 8:24 AM
Problem Name: DenTrangTri
Problem Link:
*/
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <time.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>
#include <assert.h>
#include <map>
#include <math.h>
#include <functional>
#include <set>
#include <unordered_map>
#include <numeric>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <complex>
#include <list>
#include <stack>
#include <deque>
#include <chrono>
#include <unordered_set>
#include <climits>
#pragma GCC optimize("Ofast,03","unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native,sse4")

using namespace std;

#define Chris "test"
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORD(i, a, b) for(int i = (a); i <= (b); ++i)
#define REP(i, a, b) for(int i = (a); i > (b); --i)
#define REPD(i, a, b) for(int i = (a); i >= (b); --i)
#define FORE(i, v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define all(v) (v).begin(), (v).end()
#define MARK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define Fill(v, x) fill(all((v)), (x))
#define Mem(v, a) memset((v), (a), sizeof((v)))
#define el "\n"
#define Chris_ signed main()
#define Faster ios::sync_with_stdio(false); cin.tie(nullptr);
#define showTime() cerr << '\n' << "Running time: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
#define File(Chris) if(fopen(Chris".inp", "r")){freopen(Chris".inp", "r", stdin);freopen(Chris".out", "w", stdout);}

// debug
#define debug(...) [](auto...a){ ((cerr << a << ' '), ...) << endl; }(#__VA_ARGS__, ":", __VA_ARGS__)
#define debugv(v) do { cerr << #v << " : {"; for (int izxc = 0; izxc < (int)(v).size(); ++izxc) { cerr << v[izxc]; if (izxc + 1 != (int)(v).size()) cerr << ","; } cerr << "}" << endl; } while(0)
#define DBG(x) cerr << #x << " = " << x << ' ';
#define DBGn(x) cerr << #x << " = " << x << '\n';
//

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<vii> ivi;
typedef vector<vll> ivl;

template<class X, class Y>
bool maximize(X &x, const Y &y) {
    if (x < y) {
        x = y;
        return true;
    }
    else return false;
}

template<class X, class Y>
bool minimize(X &x, const Y &y) {
    if (x > y) {
        x = y;
        return true;
    } else return false;
}

static constexpr ll mod = 1e9 + 7;
static constexpr int inf = (int) 1e5 + 5;
static constexpr ll INF = (ll) 1e9;
static constexpr ld eps = 1e-8;
static constexpr ll NINF = (ll) -1e9;
static constexpr int MAXN = (int) 1e3;
static constexpr int LOG = (int) 20;
static constexpr int base1 = (int) 131;
static constexpr int base2 = (int) 91;
static constexpr ll m2 = 1LL * mod * mod;
static constexpr ll mod_pow(ll x, ll e, ll m) { ll r = 1; x %= m; while (e > 0) { if (e & 1) r = (r * x) % m; x = (x * x) % m; e >>= 1; } return r; }

void add(int &x, int y) {
    x += y ;
    if ( x >= mod ) x -= mod ;
    if ( x < 0 ) x += mod ;
}

#define plus(a, b, m) ((((a) % (m)) + ((b) % (m))) % (m))
#define minus(a, b, m) ((((a) % (m)) - ((b) % (m))) % (m))
#define mul(a, b, m) ((((a) % (m)) * ((b) % (m))) % (m))
#define divide(a,b,m) (((ll)(a) % (m)) * mod_pow((ll)(b), (m) - 2, (m)) % (m))

static constexpr int dx[4] = {-1, 1, 0, 0};
static constexpr int dy[4] = {0, 0, -1, 1};

//#define int long long

int n, m;
int u, v;

/*
 *NX1: tong so den tat chan
 *NX2: neu ta chon 1 tap con thi moi dinh se bi doi trong thai so lan = ba cua no trong tap ding
 *NX3: chi thay doi duoc trong thanh phan lien thong
 */

void Inp(){
    cin >> n >> m;
}

void Solve() {
    Inp();
    vii s(n + 1);
    FORD(i, 1, n) cin >> s[i];
    vector<vector<pii>> adj(n + 1);
    vector<pii> edges(m + 1);
    FORD(i, 1, m){
        cin >> u >> v;
        edges[i] = {u, v};
        adj[u].pb({v, i});
        adj[v].pb({u, i});
    }
    vector<bool> visited(n + 1, 0);
    vii parent(n + 1, 0), parentEdge(n + 1, 0);
    vii bits(n + 1);
    FORD(i, 1, n) bits[i] = 1 - s[i];
    vii ans;
    vii stackv, comp, order;
    FORD(start, 1, n){
        cout << start << el;
        if (visited[start]) continue;
        stackv.clear();
        comp.clear();
        order.clear();
        visited[start] = true;
        parent[start] = 0;
        parentEdge[start] = 0;
        stackv.pb(start);
        while (!stackv.empty()){
            int u = stackv.back();
            stackv.pop_back();
            order.pb(u);
            comp.push_back(u);
            for (auto [v, idx] : adj[u]){
                if (!visited[v]){
                    visited[v] = true;
                    parent[v] = u;
                    parentEdge[v] = idx;
                    stackv.push_back(v);
                }
            }
        }
        int total_bits = 0;
        for (int s : comp) total_bits += s;
        if (total_bits & 1){
            cout << -1 << el;
            return;
        }
        for (int x : order) cout << x << " ";
        cout << el;
        REPD(i, order.size() - 1, 0){
            int u = order[i];
            if (u == start) continue;
            if (bits[u]){
                ans.pb(parentEdge[u]);
                cout << bits[u] << el;
                bits[u] ^= 1;
                bits[parentEdge[u]] ^= 1;
                cout << bits[parentEdge[u]] << el;
            }
        }
    }
    //cout << ans.size() << el;
    //for (int x : ans) cout << x << " ";
    //if (ans.empty()) cout << -1;
    return;
}

Chris_ {
    Faster
    File(Chris)

    Solve();

    showTime();

    return 0;
}