Day6 D

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define pb push_back
#define int long long
#define uint __int128
#define mp make_pair
#define left left_compile
#define right right_compile

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

const int INF = (int)1e18;
const int md = (int)1e9 + 7;
const int MAXN = (int)1e6 + 11;
const int N = (int)1e5 + 11;
const int debug = 0;
const long double eps = 1e-7;

typedef tree<
int,
null_type,
less_equal<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

int bpow(int a,int b){
    if(b == 0)
        return 1ll;
    if(b % 2 == 0){
        int t = bpow(a,b/2);
        return (t * t) % md;
    }
    return (a * bpow(a,b-1)) % md;
}

int inv(int a){ /// return 1/a by PRIME modulo md
    return bpow(a,md-2);
}

void myerase(ordered_set& st, int t){
    int r = st.order_of_key(t);
    ordered_set::iterator it = st.find_by_order(r);
    st.erase(it);
    return;
}

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

void init(){
    return;
}

struct DSU{
    int n;
    vector<int> parent;
    void init(int sz){
        n = sz;
        parent.resize(n+1);
        for(int i = 0; i <= n; i++)
            parent[i] = i;
        return;
    }
    int find_parent(int x){
        if(parent[x] == x)
            return x;
        return parent[x] = find_parent(parent[x]);
    }
    void union_sets(int a,int b){
        a = find_parent(a);
        b = find_parent(b);
        if(a == b)
            return;
        if(rnd() % 2)
            parent[a] = b;
        else
            parent[b] = a;
        return;
    }
    bool connected(int a,int b){
        return find_parent(a) == find_parent(b);
    }
};

void solve_case(){
    int n;
    cin >> n;

    vector<pair<int,pair<int,int>>> v;
    int g[n+1][n+1];
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> g[i][j];
            v.pb(mp(g[i][j],mp(i,j)));
        }
    }

    sort(v.rbegin(),v.rend());
    int sz = n - 1;
    int a,b;
    vector<pair<int,pair<int,int>>> G;
    for(int i = 0; i < sz; i++){
        cin >> a >> b;
        G.pb(mp(g[a][b],mp(a,b)));
    }

    sort(G.rbegin(),G.rend());
    DSU d[2];
    d[0].init(n+1);
    d[1].init(n+1);
    vector<pair<int,int>> ans;
    for(int i = 0; i < sz; i++){
        if(i < sz / 2){
            d[0].union_sets(G[i].second.first,G[i].second.second);
            ans.pb(mp(G[i].second.first,G[i].second.second));
        } else {
            d[1].union_sets(G[i].second.first,G[i].second.second);
        }
    }

    for(int i = 0; i < v.size(); i++){
        int x = v[i].second.first, y = v[i].second.second;
        if(d[0].connected(x,y) || d[1].connected(x,y))
            continue;
        d[0].union_sets(x,y);
        d[1].union_sets(x,y);
        ans.pb(mp(x,y));
    }

    if(ans.size() != sz){
        cout << "-1";
        return;
    }

    for(int i = 0; i < ans.size(); i++){
        cout << ans[i].first << " " << ans[i].second << "\n";
    }

    return;
}

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    freopen("treexor.in","r",stdin);
    freopen("treexor.out","w",stdout);

    init();

    int tests = 1;
//    cin >> tests;

    for(int _ = 1; _ <= tests; _++){
        solve_case();
    }

    return 0;
}

/*


*/