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:
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


enum Type{
	IN_KADO,
	IN_HEN,
	IN_NAIBU,
};

struct Info{
	void set(Type arg_type){
		type = arg_type;
	}
	Type type;
};


int main(){

	int N;
	scanf("%d",&N);

	int* in_num = new int[N*N];
	bool* used = new bool[N*N];
	Info* loc = (Info*)malloc(sizeof(Info)*(N*N));

	for(int i = 0; i < N*N; i++){
		in_num[i] = 0;
		used[i] = false;
	}

	vector<int> ADJ[N*N];

	int a,b,limit = 2*N*N-2*N;
	for(int loop = 0; loop < limit; loop++){
		scanf("%d %d",&a,&b);
		a--;
		b--;
		in_num[a]++;
		in_num[b]++;
		ADJ[a].push_back(b);
		ADJ[b].push_back(a);
	}

	vector<int> KADO;
	for(int i = 0; i < N*N; i++){
		if(in_num[i] == 2){
			KADO.push_back(i);
			loc[i].set(IN_KADO);
		}else if(in_num[i] == 3){
			loc[i].set(IN_HEN);
		}else{
			loc[i].set(IN_NAIBU);
		}
	}

	int** ans_table = new int*[N];
	for(int row = 0; row < N; row++){
		ans_table[row] = new int[N];
	}

	ans_table[0][0] = KADO[0];
	used[KADO[0]] = true;

	int tmp_num;

	for(int row = 1; row <= N-2; row++){
		for(int i = 0; i < ADJ[ans_table[row-1][0]].size(); i++){
			tmp_num = ADJ[ans_table[row-1][0]][i];
			if(loc[tmp_num].type == IN_HEN && used[tmp_num] == false){
				ans_table[row][0] = tmp_num;
				used[tmp_num] = true;
				break;
			}
		}
	}

	for(int i = 0; i < ADJ[ans_table[N-2][0]].size(); i++){
		tmp_num = ADJ[ans_table[N-2][0]][i];
		if(loc[tmp_num].type == IN_KADO && used[tmp_num] == false){
			ans_table[N-1][0] = tmp_num;
			used[tmp_num] = true;
			break;
		}
	}

	bool FLG;

	for(int col = 1; col <= N-2; col++){

		for(int i = 0; i < ADJ[ans_table[0][col-1]].size(); i++){
			tmp_num = ADJ[ans_table[0][col-1]][i];
			if(loc[tmp_num].type == IN_HEN && used[tmp_num] == false){
				ans_table[0][col] = tmp_num;
				used[tmp_num] = true;
				break;
			}
		}

		for(int row = 1; row <= N-2; row++){

			for(int i = 0; i < ADJ[ans_table[row-1][col]].size(); i++){
				tmp_num = ADJ[ans_table[row-1][col]][i];
				if(loc[tmp_num].type != IN_NAIBU || used[tmp_num] == true)continue;

				FLG = false;
				for(int k = 0; k < ADJ[ans_table[row][col-1]].size(); k++){
					if(tmp_num == ADJ[ans_table[row][col-1]][k]){
						FLG = true;
						break;
					}
				}

				if(FLG){
					ans_table[row][col] = tmp_num;
					used[tmp_num] = true;
					break;
				}
			}
		}

		for(int i = 0; i < ADJ[ans_table[N-1][col-1]].size(); i++){
			tmp_num = ADJ[ans_table[N-1][col-1]][i];
			if(loc[tmp_num].type == IN_HEN && used[tmp_num] == false){
				ans_table[N-1][col] = tmp_num;
				used[tmp_num] = true;
				break;
			}
		}
	}

	for(int i = 0; i < ADJ[ans_table[0][N-2]].size(); i++){
		tmp_num = ADJ[ans_table[0][N-2]][i];
		if(loc[tmp_num].type == IN_KADO && used[tmp_num] == false){
			ans_table[0][N-1] = tmp_num;
			used[tmp_num] = true;
			break;
		}
	}

	for(int row = 1; row <= N-2; row++){
		for(int i = 0; i < ADJ[ans_table[row-1][N-1]].size(); i++){
			tmp_num = ADJ[ans_table[row-1][N-1]][i];
			if(loc[tmp_num].type == IN_HEN && used[tmp_num] == false){
				ans_table[row][N-1] = tmp_num;
				used[tmp_num] = true;
				break;
			}
		}
	}

	for(int i = 0; i < ADJ[ans_table[N-1][N-2]].size(); i++){
		tmp_num = ADJ[ans_table[N-1][N-2]][i];
		if(loc[tmp_num].type == IN_KADO && used[tmp_num] == false){
			ans_table[N-1][N-1] = tmp_num;
			break;
		}
	}


	for(int row = 0; row <= N-1; row++){
		printf("%d",ans_table[row][0]+1);
		for(int col = 1; col <= N-1; col++){
			printf(" %d",ans_table[row][col]+1);
		}
		printf("\n");
	}

	return 0;
}