#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 1234567890

struct Vrchol {
    Vrchol() : depth(-1), best(INF), c1(0), c2(0) {}
    int type;
    vector<int> next;
    int depth;
    int best;
    int c1, c2;
};
vector<Vrchol> v;             // Vrcholy grafu
vector<pair<int, int>> mosty; // Kandidáti na mosty: (index hrany, index jejího cíle)

// Prohledá vrchol x, vrátí trojici (best, c1, c2) daného vrcholu,
// případně (depth, 0, 0), pokud jsme tam už byli.
pair<int, pair<int, int>> dfs(int x, int depth, int odkud) {
    if (v[x].depth != -1)
        return make_pair(v[x].depth, make_pair(0, 0));
    v[x].depth = depth;
    for (int i = 0; i < v[x].next.size(); i++) {
        if (v[x].next[i] == odkud) continue;
        pair<int, pair<int, int>> ret = dfs(v[x].next[i], depth+1, x);
        v[x].best = min(v[x].best, ret.first);
        v[x].c1 += ret.second.first;
        v[x].c2 += ret.second.second;
    }
    if (v[x].type == 1) v[x].c1++;
    if (v[x].type == 2) v[x].c2++;
    if (v[x].best >= v[x].depth && depth != 0)
        mosty.push_back(make_pair(odkud, x));
    return make_pair(v[x].best, make_pair(v[x].c1, v[x].c2));
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    v.resize(n);
    for (int i = 0; i < n; i++) scanf("%d", &v[i].type);
    for (int i = 0; i < m; i++) {
        int a, b;
	scanf("%d %d", &a, &b);
        a--; b--;
        if (v[a].type == 0 || v[b].type == 0) continue;
        v[a].next.push_back(b);
        v[b].next.push_back(a);
    }

    for (int i = 0; i < n; i++) {
        mosty.clear();
        dfs(i, 0, -1);
        int C1 = v[i].c1,  C2 = v[i].c2;
        for (int j = 0; j < mosty.size(); j++) {
            if (v[mosty[j].second].c1 > 0 &&
                v[mosty[j].second].c2 == 0 &&
                C2 > 0)
                printf("%d %d\n", mosty[j].first+1, mosty[j].second+1);
            if (C1 - v[mosty[j].second].c1 > 0 &&
                C2 - v[mosty[j].second].c2 == 0 &&
                v[mosty[j].second].c2 > 0)
                printf("%d %d\n", mosty[j].first+1, mosty[j].second+1);
        }
    }

    return 0;
}