#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;
}

Measured memory_bytes: 3936