#include "worldmap.h"
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<int>a, b;
namespace sub1{
vector<vector<int>>solve(){
vector<vector<int>>ans(n, vector<int>(n));
for(int i = 0; i < n; i++){
iota(ans[i].begin(), ans[i].end(), 1 + (i & 1));
}
for(int i = 1; i < n; i += 2){
ans[i].back() = n - 1;
}
return ans;
}
}
namespace sub2{
vector<vector<int>>solve(){
vector<vector<int>>g(n + 1);
for(int i = 0; i < m; i++){
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
}
vector<int>tour;
function<void(int, int)>dfs;
dfs = [&] (int s, int p){
tour.push_back(s);
for(int& d : g[s]){
if(d != p){
dfs(d, s);
tour.push_back(s);
}
}
};
dfs(1, -1);
int N = tour.size();
vector<vector<int>>ans(N, vector<int>(N));
for(int i = 0; i < N; i++){
iota(ans[i].begin(), ans[i].end(), i & 1);
}
for(int i = 1; i < N; i += 2){
ans[i].back() = 0;
}
for(int i = 0; i < N; i++){
for(int& j : ans[i]){
j = tour[j];
}
}
return ans;
}
}
namespace sub3{
bitset<51>need[51];
vector<vector<int>>solve(){
vector<vector<int>>ans(n, vector<int>(n));
for(int i = ans[0][0] = 1; i <= n; i++){
need[i].set();
need[i][i] = false;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == 0 && j == 0){
continue;
}
bitset<51>avai;
avai.reset();
if(j > 0){
avai |= need[ans[i][j - 1]];
}
if(i > 0){
avai |= need[ans[i - 1][j]];
}
bool flag = true;
for(int k = 1; k <= n; k++){
if(avai[k]){
ans[i][j] = k;
if(j > 0){
need[ans[i][j - 1]][k] = false;
}
if(i > 0){
need[ans[i - 1][j]][k] = false;
}
flag = false;
break;
}
}
if(flag){
int best = 1;
for(int k = 2; k <= n; k++){
if(need[k].count() > need[best].count()){
best = k;
}
}
ans[i][j] = best;
}
}
}
return ans;
}
}
namespace sub4{
bool check_subtask(){
vector<bool>cnt(n + 1, false);
cnt[0] = cnt[1] = true;
for(int i = 0; i < m; i++){
if(min(a[i], b[i]) == 1){
cnt[a[i] ^ b[i] ^ 1] = true;
}
}
return find(cnt.begin(), cnt.end(), false) == cnt.end();
}
vector<vector<int>>solve(){
int N = n << 1;
vector<vector<int>>ans(N, vector<int>(N, 1));
for(int i = 0, j = 0; i < N; i += 2){
for(int k = 0; k + 1 < N && j < m; k += 3, j++){
ans[i][k] = a[j];
ans[i][k + 1] = b[j];
}
}
return ans;
}
}
namespace sub56{
vector<vector<int>>solve(){
vector<vector<int>>g(n + 1), f(n + 1);
vector<vector<bool>>have(n + 1, vector<bool>(n + 1, false));
for(int i = 0; i < m; i++){
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
have[a[i]][b[i]] = have[b[i]][a[i]] = true;
}
vector<int>tour, par(n + 1, -1);
int tdfs = par[1] = 0;
function<void(int)>dfs;
dfs = [&] (int s){
for(int x = par[s]; x != 0; x = par[x]){
f[s].push_back(x);
f[s].push_back(x);
}
tour.push_back(s);
for(int& d : g[s]){
if(d != par[s]){
if(par[d] == -1){
par[d] = s;
dfs(d);
tour.push_back(s);
}
}
}
for(int i = 2; i < f[s].size(); i += 2){
if(have[s][f[s][i]]){
if(i + 2 < f[f[s][i + 1] = s].size() && !have[s][f[s][i + 2]]){
f[s][i + 2] = f[s][i];
i += 2;
}
}
}
vector<int>temp((n << 1) - int(f[s].size()), s);
f[s].insert(f[s].begin(), temp.begin(), temp.end());
};
dfs(1);
vector<vector<int>>ans;
for(int& i : tour){
ans.push_back(f[i]);
}
ans.push_back(ans.back());
return ans;
}
}
vector<vector<int>>create_map(int __n, int __m, vector<int>__a, vector<int>__b){
swap(a, __a);
swap(b, __b);
if((m = __m) == (n = __n) - 1){
bool is_sub1 = true;
for(int i = 0; i < m; i++){
if(a[i] != i + 1 || b[i] != i + 2){
is_sub1 = false;
break;
}
}
return is_sub1 ? sub1::solve() : sub2::solve();
}
if((m << 1) == (n * (n + 1))){
return sub3::solve();
}
if(sub4::check_subtask()){
return sub4::solve();
}
return sub56::solve();
}
