Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	io := NewIo()
	defer io.Flush()
	N := io.NextInt()
	nodes := make([]Node, N*N+1)
	for i := 0; i < 2*N*N-2*N; i++ {
		a, b := io.NextInt(), io.NextInt()
		nodes[a].adj = append(nodes[a].adj, b)
		nodes[b].adj = append(nodes[b].adj, a)
	}
	ninja(nodes, N, io)
}

type Node struct {
	adj []int
}

func ninja(nodes []Node, N int, io *Io) {
	used := make([]bool, N*N+1)
	m := make([][]int, N)
	fst := 0
	for i := 0; i < N; i++ {
		m[i] = make([]int, N)
		for j := 0; j < N; j++ {
			if len(nodes[i*N+j].adj) == 2 {
				fst = i*N + j
			}
		}
	}
	m[0][0] = fst
	used[fst] = true
	for j := 1; j < N; j++ {
		u := 0
		deg := 3
		if j == N-1 {
			deg = 2
		}
		for _, v := range nodes[m[0][j-1]].adj {
			if !used[v] && len(nodes[v].adj) == deg {
				u = v
			}
		}
		m[0][j] = u
		used[u] = true
	}
	for i := 1; i < N; i++ {
		for j := 0; j < N; j++ {
			u := 0
			for _, v := range nodes[m[i-1][j]].adj {
				if !used[v] {
					u = v
				}
			}
			m[i][j] = u
			used[u] = true
		}
	}
	for _, a := range m {
		io.PrintIntSlice(a)
	}
}

// I/O template
type Io struct {
	reader    *bufio.Reader
	writer    *bufio.Writer
	tokens    []string
	nextToken int
}

func NewIo() *Io {
	return &Io{
		reader: bufio.NewReader(os.Stdin),
		writer: bufio.NewWriter(os.Stdout),
	}
}

func (io *Io) Flush() {
	err := io.writer.Flush()
	if err != nil {
		panic(err)
	}
}

func (io *Io) NextLine() string {
	var buff []byte
	for {
		line, isPrefix, err := io.reader.ReadLine()
		if err != nil {
			panic(err)
		}
		buff = append(buff, line...)
		if !isPrefix {
			break
		}
	}
	return string(buff)
}

func (io *Io) Next() string {
	for io.nextToken >= len(io.tokens) {
		line := io.NextLine()
		io.tokens = strings.Fields(line)
		io.nextToken = 0
	}
	s := io.tokens[io.nextToken]
	io.nextToken++
	return s
}

func (io *Io) NextInt() int {
	i, err := strconv.Atoi(io.Next())
	if err != nil {
		panic(err)
	}
	return i
}

func (io *Io) NextFloat() float64 {
	i, err := strconv.ParseFloat(io.Next(), 64)
	if err != nil {
		panic(err)
	}
	return i
}

func (io *Io) Println(a ...interface{}) {
	fmt.Fprintln(io.writer, a...)
}

func (io *Io) Printf(format string, a ...interface{}) {
	fmt.Fprintf(io.writer, format, a...)
}

func (io *Io) PrintIntSlice(a []int) {
	b := []interface{}{}
	for _, x := range a {
		b = append(b, x)
	}
	io.Println(b...)
}

func (io *Io) PrintStringSlice(a []string) {
	b := []interface{}{}
	for _, x := range a {
		b = append(b, x)
	}
	io.Println(b...)
}

func Log(name string, value interface{}) {
	fmt.Fprintf(os.Stderr, "%s=%+v\n", name, value)
}

func ExampleIo() {
	io := NewIo()
	defer io.Flush()
	a := make([]int, 0, 3)
	a[0], a[1], a[2] = io.NextInt(), io.NextInt(), io.NextInt()
	io.Println(a)
	io.PrintIntSlice(a)
	Log("io", a)
}

C++: #include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

class Graph{
	private:
	int n;
	vvp g;
	public:
	vi DIJ(int s){
		priority_queue<P> q;
		vi d(n,inf);
		d[s]=0;
		q.push({0,s});
		while(!q.empty()){
			P p=q.top();
			q.pop();
			int v=p.second;
			if(d[v]<-p.first) continue;
			for(auto i:g[v]){
				int u=i.first,D=d[v]+i.second;
				if(d[u]>D){
					d[u]=D;
					q.push({-D,u});
				}
			}
		}
		return d;
	}
	Graph(int v){
		n=v;
		g=vvp(v);
	}
	void add_edge(int s,int t,int c){
		g[s].push_back({t,c});
		g[t].push_back({s,c});
	}
};

int n;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	Graph g(n*n);
	vi d(n*n);
	for(int i=0;i<2*n*n-2*n;i++){
		int u,v;
		cin>>u>>v;
		u--;v--;
		g.add_edge(u,v,1);
		d[u]++;d[v]++;
	}
	int x,y;
	for(int i=0;i<n*n;i++) if(d[i]==2) x=i;
	vi a=g.DIJ(x);
	for(int i=0;i<n*n;i++) if(d[i]==2&&a[i]==n-1) y=i;
	vvi c(n,vi(n));
	vi b=g.DIJ(y);
	for(int i=0;i<n*n;i++){
		int p=a[i],q=b[i];
		c[(p+q-n+1)/2][p-(p+q-n+1)/2]=i;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++) cout<<c[i][j]+1<<" \n"[j==n-1];
	}
}

C++: #include <bits/stdc++.h>

using namespace std;

typedef tuple<int, int, int> TP;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

int N;
vector<vector<int>> city;

int main() {
  cin >> N;
  city.assign(N * N, vector<int>());
  for (int i = 0; i < 2 * N * N - 2 * N; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    city[a].push_back(b);
    city[b].push_back(a);
  }

  vector<vector<int>> ans(N, vector<int>(N, -1));
  vector<bool> used(N * N, false);
  for (int i = 0; i < N * N; i++) {
    if (city[i].size() == 2) {
      ans[0][0] = i;
      used[i] = true;

      for (int j = 0; j < N - 1; j++) {
        int index = -1, deg = 1e9;
        for (auto nv : city[ans[0][j]]) {
          if (used[nv]) continue;
          if (city[nv].size() < deg) {
            index = nv;
            deg = city[nv].size();
          }
        }
        used[index] = true;
        ans[0][j + 1] = index;
      }

      for (int y = 0; y < N - 1; y++) {
        for (int x = 0; x < N; x++) {
          int v = ans[y][x];
          for (auto nv : city[v]) {
            if (used[nv]) continue;
            ans[y + 1][x] = nv;
            used[nv] = true;
          }
        }
      }

      for (int y = 0; y < N; y++) {
        for (int x = 0; x < N; x++) {
          cout << ans[y][x] + 1 << " ";
        }
        cout << endl;
      }
      break;
    }
  }

  return 0;
}

C++: /*  -*- coding: utf-8 -*-
 *
 * 2847.cc: Ninja Map
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100;
const int MAX_NN = MAX_N * MAX_N;

/* typedef */

typedef vector<int> vi;

/* global variables */

vi nbrs[MAX_NN];
int xs[MAX_NN], ys[MAX_NN], flds[MAX_N][MAX_N];

/* subroutines */

void printflds(int n) {
  for (int y = 0; y < n; y++) {
    for (int x = 0; x < n; x++) {
      if (x) putchar(' ');
      printf("%d", flds[y][x] + 1);
    }
    putchar('\n');
  }
}

/* main */

int main() {
  int n;
  scanf("%d", &n);

  int nn = n * n;
  int m = 2 * nn - 2 * n;

  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--, b--;
    nbrs[a].push_back(b);
    nbrs[b].push_back(a);
  }

  memset(xs, -1, sizeof(xs));
  memset(ys, -1, sizeof(ys));
  memset(flds, -1, sizeof(flds));

  int st = -1;
  for (int i = 0; st < 0 && i < nn; i++)
    if (nbrs[i].size() == 2) st = i;
  xs[st] = ys[st] = 0;
  flds[0][0] = st;
  //printf("st=%d\n", st);

  for (int i = nbrs[st][0], x = 1;; x++) {
    xs[i] = x, ys[i] = 0;
    flds[0][x] = i;
    vi &nbri = nbrs[i];
    if (nbri.size() < 3) break;

    int j = -1;
    for (vi::iterator vit = nbri.begin(); vit != nbri.end(); vit++)
      if (xs[*vit] < 0 && nbrs[*vit].size() < 4) {
	j = *vit;
	break;
      }
    i = j;
  }

  for (int y = 1; y < n; y++)
    for (int x = 0; x < n; x++) {
      int u = flds[y - 1][x];
      vi &nbru = nbrs[u];
      int v = -1;
      for (vi::iterator vit = nbru.begin(); vit != nbru.end(); vit++)
	if (xs[*vit] < 0) {
	  v = *vit;
	  break;
	}

      xs[v] = x, ys[v] = y;
      flds[y][x] = v;
    }
  printflds(n);
  
  return 0;
}