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 <bits/stdc++.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repp(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perr(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)

typedef long long LL;
typedef long double LD;

int main(){
  int n;
  cin >> n;
  if(n==2){
    int m=2*n*n-2*n;
    vector<vector<int>> e(n*n);
    int u,v;
    rep(i,m){
      cin >> u >> v;
      e[u-1].push_back(v-1);
      e[v-1].push_back(u-1);
    }
    vector<int> dist(n*n,-1);
    queue<int> q;
    q.push(0);
    dist[0]=0;
    while(!q.empty()){
      int now=q.front();
      q.pop();
      for(auto nx:e[now]){
        if(dist[nx]!=-1) continue;
        dist[nx]=dist[now]+1;
        q.push(nx);
      }
    }
    vector<vector<int>> ans(n,vector<int>(n,-1));
    rep(i,4){
      if(dist[i]==0) ans[0][0]=i;
      else if(dist[i]==2) ans[1][1]=i;
      else{
        if(ans[0][1]==-1) ans[0][1]=i;
        else ans[1][0]=i;
      }
    }
    rep(i,n){
      rep(j,n){
        cout << ans[i][j]+1;
        if(j<n-1) cout << " ";
        else cout << endl;
      }
    }
    return 0;
  }
  vector<vector<int>> e(n*n);
  int m=2*n*n-2*n;
  int u,v;
  rep(i,m){
    cin >> u >> v;
    e[u-1].push_back(v-1);
    e[v-1].push_back(u-1);
  }
  int s;
  rep(i,n*n){
    if(e[i].size()==2){
      s=i;
      break;
    }
  }
  vector<int> par(n*n,-1);
  vector<int> dist(n*n,-1);
  queue<int> q;
  q.push(s);
  dist[s]=0;
  par[s]=s;
  int t;
  while(!q.empty()){
    int now=q.front();
    q.pop();
    for(auto nx:e[now]){
      if(dist[nx]!=-1) continue;
      dist[nx]=dist[now]+1;
      par[nx]=now;
      if(dist[nx]==n-1&&e[nx].size()==2){
        t=nx;
        goto next;
      }
      q.push(nx);
    }
  }
  next:;
  vector<bool> usd(n*n,false);
  vector<vector<int>> ans(n,vector<int>(n,-1));
  per(i,n){
    ans[0][i]=t;
    usd[t]=true;
    t=par[t];
  }
  rep(i,n-1){
    rep(j,n){
      for(auto nx:e[ans[i][j]]){
        if(!usd[nx]){
          ans[i+1][j]=nx;
          usd[nx]=true;
          break;
        }
      }
    }
  }
  rep(i,n){
    rep(j,n){
      cout << ans[i][j]+1;
      if(j<n-1) cout << " ";
      else cout << endl;
    }
  }
  return 0;
}