#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define lint long long
#define pii pair<int,int>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define SZ(v) ((int)v.size())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MINF(a) memset(a,0x3f,sizeof(a))
#define POW(n) (1LL<<(n))
#define POPCNT(n) (__builtin_popcount(n))
#define IN(i,a,b) (a <= i && i <= b)
using namespace std;
template <typename T> inline bool CHMIN(T& a,T b) { if(a>b) { a=b; return 1; } return 0; }
template <typename T> inline bool CHMAX(T& a,T b) { if(a<b) { a=b; return 1; } return 0; }
template <typename T> inline void SORT(T& a) { sort(ALL(a)); }
template <typename T> inline void REV(T& a) { reverse(ALL(a)); }
template <typename T> inline void UNI(T& a) { sort(ALL(a)); a.erase(unique(ALL(a)),a.end()); }
template <typename T> inline T LB(vector<T>& v, T a) { return *lower_bound(ALL(v),a); }
template <typename T> inline int LBP(vector<T>& v, T a) { return lower_bound(ALL(v),a) - v.begin(); }
template <typename T> inline T UB(vector<T>& v, T a) { return *upper_bound(ALL(v),a); }
template <typename T> inline int UBP(vector<T>& v, T a) { return upper_bound(ALL(v),a) - v.begin(); }
template <typename T1, typename T2> ostream& operator<< (ostream& os, const pair<T1,T2>& p) { os << p.first << " " << p.second; return os; }
template <typename T1, typename T2> istream& operator>> (istream& is, pair<T1,T2>& p) { is >> p.first >> p.second; return is; }
template <typename T> ostream& operator<< (ostream& os, const vector<T>& v) { REP(i,v.size()) { if (i) os << " "; os << v[i]; } return os; }
template <typename T> istream& operator>> (istream& is, vector<T>& v) { for(T& in : v) is >> in; return is; }
template <typename T = int> vector<T> make_v(size_t a) { return vector<T>(a); }
template <typename T, typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); }
template <typename T, typename V> typename enable_if<is_class<T>::value == 0>::type fill_v(T &t, const V &v) { t = v; }
template <typename T, typename V> typename enable_if<is_class<T>::value != 0>::type fill_v(T &t, const V &v) { for(auto &e : t) fill_v(e,v); }
const lint MOD = 1000000007;
const lint INF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-10;

const int dy[] = {-1, 0, 0, 1};
const int dx[] = {0, -1, 1, 0};
int N;
int a[20010], b[20010];
vector<int> g[10010];
int s[110][110];
bool used[10010];
pii pos[10010];

bool check(int i, int y, int x) {
    if (i == 0) return x < N - 1;
    if (i == 1) return y < N - 1;
    if (i == 2) return x > 0;
    return y > 0;
}

pii calcNext(int i, int y, int x) {
    if (i == 0) return {y, x + 1};
    if (i == 1) return {y + 1, x};
    if (i == 2) return {y, x - 1};
    return {y - 1, x};
}

void _main() {
    cin >> N;
    REP(i, 2 * N * N - 2 * N) {
        cin >> a[i] >> b[i];
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }

    int c;
    FOR(i, 1, N * N + 1) {
        if (SZ(g[i]) == 2) {
            c = i;
            break;
        }
    }

    MINUS(s);
    int y = 0, x = 0;
    s[y][x] = c;
    used[c] = true;

    REP(k, 4) {
        FOR(i, 0 + (k == 3), N - 1) {
            for (int j : g[c]) if (!used[j]) {
                int ny, nx;
                tie(ny, nx) = calcNext(k, y, x);
                bool flag = check(k, ny, nx);
                if ((flag && SZ(g[j]) == 3) || (!flag && SZ(g[j]) == 2)) {
                    c = j;
                    s[ny][nx] = c;
                    used[c] = true;
                    y = ny; x = nx;
                    pos[c] = {y, x};
                    break;
                }
            }
        }
    }

    queue<int> que;
    REP(k, N) {
        for (int j = k; j < N - k; ++j) que.push(s[k][j]);
        for (int i = k + 1; i < N - k; ++i) que.push(s[i][N - k - 1]);
        for (int j = N - k - 1; j >= k; --j) que.push(s[N - 1 - k][j]);
        for (int i = N - k - 1; i >= k + 1; --i) que.push(s[i][k]);
        while (!que.empty()) {
            int p = que.front(); que.pop();
            int y, x;
            tie(y, x) = pos[p];
            int val = -1;
            for (int j : g[p]) {
                if (!used[j]) val = j;
            }
            if (val < 0) continue;
            REP(l, 4) {
                int ny = y + dy[l];
                int nx = x + dx[l];
                if (IN(ny, 0, N - 1) && IN(nx, 0, N - 1) && s[ny][nx] < 0) {
                    s[ny][nx] = val;
                    used[val] = true;
                    pos[val] = {ny, nx};
                    break;
                }
            }
        }
    }



    REP(i, N) REP(j, N) {
        cout << s[i][j] << " \n"[j+1==N];
    }
    
}

signed main(signed argc, char **argv) {
    if (argc > 1) {
        if (strchr(argv[1], 'i'))
            freopen("input.txt", "r", stdin);
        if (strchr(argv[1], 'o'))
            freopen("output.txt", "w", stdout);
    }
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    _main();
    return 0;
}


Measured memory_bytes: 4496