Problem: Intersections of Crossing Path City are aligned to a grid. There are $N$ east-west streets which are numbered from 1 to $N$, from north to south. There are also $N$ north-south streets which are numbered from 1 to $N$, from west to east. Every pair of east-west and north-south streets has an intersection; therefore there are $N^2$ intersections which are numbered from 1 to $N^2$.

Surprisingly, all of the residents in the city are Ninja. To prevent outsiders from knowing their locations, the numbering of intersections is shuffled.

You know the connections between the intersections and try to deduce their positions from the information. If there are more than one possible set of positions, you can output any of them.



Input

The input consists of a single test case formatted as follows.


$N$
$a_1$ $b_1$
...
$a_{2N^2−2N}$ $\;$ $b_{2N^2−2N}$


The first line consists of an integer $N$ ($2 \leq N \leq 100$). The following $2N^2 - 2N$ lines represent connections between intersections. The ($i+1$)-th line consists of two integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq N^2, a_i \ne b_i$), which represent that the $a_i$-th and $b_i$-th intersections are adjacent. More precisely, let's denote by ($r, c$) the intersection of the $r$-th east-west street and the $c$-th north-south street. If the intersection number of ($r,c$) is $a_i$ for some $r$ and $c$, then the intersection number of either ($r-1, c$), ($r+1, c$), ($r, c-1$) or ($r, c+1$) must be $b_i$. All inputs of adjacencies are different, i.e., ($a_i, b_i$) $\ne$ ($a_j, b_j$) and ($a_i, b_i$) $\ne$ ($b_j, a_j$) for all $1 \leq i < j \leq 2N^2-2N$. This means that you are given information of all adjacencies on the grid.

The input is guaranteed to describe a valid map.

Output

Print a possible set of positions of the intersections. More precisely, the output consists of $N$ lines each of which has space-separated $N$ integers. The $c$-th integer of the $r$-th line should be the intersection number of ($r, c$).

If there are more than one possible set of positions, you can output any of them.

Examples

Input

3
1 2
4 7
8 6
2 3
8 9
5 3
4 6
5 6
7 8
1 4
2 6
5 9


Output

7 4 1
8 6 2
9 5 3


Input

4
12 1
3 8
10 7
13 14
8 2
9 12
6 14
11 3
3 13
1 10
11 15
4 15
4 9
14 10
5 7
2 5
6 1
14 5
16 11
15 6
15 13
9 6
16 4
13 2


Output

8 2 5 7
3 13 14 10
11 15 6 1
16 4 9 12

Solution (in CPP):

Solution:
#define  _CRT_SECURE_NO_WARNINGS
#pragma comment (linker, "/STACK:526000000")

#include "bits/stdc++.h"

using namespace std;
typedef string::const_iterator State;
#define eps 1e-11L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL

#define MOD 998244353LL
#define seg_size 262144*2LL
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()

unsigned long xor128() {
	static unsigned long x = 123456789, y = 362436069, z = 521288629, w = time(NULL);
	unsigned long t = (x ^ (x << 11));
	x = y; y = z; z = w;
	return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

void init() {
	iostream::sync_with_stdio(false);
	cout << fixed << setprecision(20);
}
#define int ll

vector<int> vertexs[20000];
int used[20000];
int ans[100][100];
void solve() {
	int n;
	cin >> n;
	REP(i, 2 * n * n - 2 * n) {
		int a, b;
		cin >> a >> b;
		vertexs[a].push_back(b);
		vertexs[b].push_back(a);
	}
	int starter = 0;
	REP(i, n * n + 1) {
		if (vertexs[i].size() == 2) {
			starter = i;
			break;
		}
	}
	ans[0][0] = starter;
	used[starter] = 1;
	int xe[4] = { 0,1,0,-1 };
	int ye[4] = { 1,0,-1,0 };
	pair<int, int> now_itr = mp(0, 0);
	int dir = 0;
	REP(q, 3 + (n - 2) * 4) {
		int next = 0;
		for (auto x : vertexs[starter]) {
			if (used[x] == 0&&vertexs[x].size() >= 1 && vertexs[x].size() <= 3) {
				next = x;
				break;
			}
		}
		while (true) {
			pair<int, int> next_go = mp(now_itr.first + xe[dir], now_itr.second + ye[dir]);
			if (next_go.first >= 0 && next_go.first < n && next_go.second >= 0 && next_go.second < n) {
				now_itr = next_go;
				break;
			}
			dir++;
		}
		ans[now_itr.first][now_itr.second] = next;
		starter = next;
		used[starter] = 1;
	}
	for (int i = 1; i < n - 1; ++i) {
		for (int q = 1; q < n - 1; ++q) {
			map<int, int> cnter;
			for (auto x : vertexs[ans[i - 1][q]]) {
				cnter[x]++;
			}
			for (auto x : vertexs[ans[i][q - 1]]) {
				cnter[x]++;
			}
			for (auto x : cnter) {
				if (used[x.first] == 0 && x.second >= 2) {
					used[x.first] = 1;
					ans[i][q] = x.first;
					break;
				}
			}
		}
	}
	REP(i, n) {
		REP(q, n) {
			if (q != 0) cout << " ";
			cout << ans[i][q];
		}
		cout << endl;
	}
}

#undef int
int main() {
	init();
	solve();
}