#include "worldmap.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
typedef long long int lld;
int c;
int n;
vector<int> nei[1'000'000];
bool vis[1'000'000];
int table[1000][1000];
bool parity;
int row;
void transition(int X, int Y){
// cout<<"T "<<X<<" "<<Y<<endl;
rep(i,0,c){
if((parity^(i&1))){
table[row][i]=X;
}else{
table[row][i]=Y;
}
}
row+=1;
// parity^=1;
}
void DFS(int node){
if(!vis[node]){
// cout<<"N "<<node<<endl;
int C=0;
rep(i,0,c){
if((parity^(i&1))){
table[row][i]=nei[node][C%nei[node].size()];
C+=1;
}else{
table[row][i]=node;
}
}
row+=1;
parity^=1;
}
vis[node]=true;
trav(a,nei[node]){
if(!vis[a]){
transition(a,node);
DFS(a);
transition(node,a);
}
}
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
n=N;
c=3*n;
rep(i,0,c){
rep(j,0,c){
table[i][j]=0;
}
}
rep(i,0,M)A[i]--,B[i]--;
rep(i,0,n)nei[i].clear();
rep(i,0,M){
nei[A[i]].push_back(B[i]);
nei[B[i]].push_back(A[i]);
}
rep(i,0,n)vis[i]=false;
parity=false;
row=0;
if(N>1)DFS(0);
vector<vector<int> > ans(c);
rep(i,0,c){
ans[i].resize(c);
rep(j,0,c){
ans[i][j]=table[i][j]+1;
}
}
return ans;
}
