#include "worldmap.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
vector<int>j;
map<pair<int,int>,int>mp;
//const int N1=50;
vector<int>v[500];
//#include "worldmap.h"
int x[500];
int yuuu;
int bati[500][500];
void dfs(int a,int parent){
x[a]=1;
for(int to:v[a]) {
if(x[to]==0) {
j.push_back(a);
dfs(to, a);
}
}
if(a!=1){
j.push_back(a);
}
}
vector<vector<int>>create_map(int N, int M,vector<int> A,vector<int> B) {
int n=M;
if(M==N-1){
for(int i=1; i<=N; i++){
v[i].clear();
}
j.clear();
int n=A.size();
for(int i=0; i<n; i++){
v[A[i]].push_back(B[i]);
v[B[i]].push_back(A[i]);
}
for(int i=1; i<=N; i++) x[i]=0;
dfs(1,0);
for(int i=1;i<=N; i++) if(x[i]==0)dfs(i,0);
int batiii=j.size();
vector<vector<int>> ans(batiii, vector<int>(batiii));
for(int i=0; i<j.size(); i++){
for(int drnachvi=0; drnachvi<j.size(); drnachvi++){
ans[drnachvi][i]=j[i];
//cout<<ans[drnachvi][i]<<" ";
}
//cout<<endl;
}
return ans;
exit(0);
}
else{
for(int i=0; i<=N; i++){
v[i].clear();
}
yuuu=N;
j.clear();
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
bati[i][j]=0;
}
}
for(int i=0; i<M; i++){
v[A[i]].push_back(B[i]);
v[B[i]].push_back(A[i]);
bati[A[i]][B[i]]=1;
bati[B[i]][A[i]]=1;
}
for(int i=0; i<500; i++){
x[i]=0;
}
j.clear();
dfs(1,0);
//for(int u=1; u<=N; u++) if(x[u]==0) dfs(u,0);
// for(auto a:j){
// cout<<a<<" ";
// }
// cout<<endl;
for(int u=1; u<=N; u++){
if(x[u]==0)dfs(u,0);
}
vector<int>drnachvi;
drnachvi.clear();
mp.clear();
int ku=j.size();
int mtvleli=0;
int zuigetsu[N+1];
for(int i=0; i<=N; i++){
zuigetsu[i]=0;
}
for(int i=0; i<M; i++){
// v[A[i]].push_back(B[i]);
// v[B[i]].push_back(A[i]);
bati[A[i]][B[i]]=1;
bati[B[i]][A[i]]=1;
}
for(int i=0; i<j.size(); i++){
drnachvi.push_back(j[i]);
if(zuigetsu[j[i]]==0){
drnachvi.push_back(-19);
drnachvi.push_back(j[i]);
zuigetsu[j[i]]=1;
mtvleli++;
if(mtvleli==N)break;
}
}
if(mtvleli<N){
for(int u=1; u<=N; ++u){
if(zuigetsu[u]==0){
drnachvi.push_back(u);
drnachvi.push_back(-19);
drnachvi.push_back(u);
zuigetsu[u]=1;
mtvleli++;
if(mtvleli==N) break;
}
}
}
int batiii=drnachvi.size();
vector<vector<int>> ans(batiii, vector<int>(batiii,-19));
for(int i=0; i<batiii; i++){
ans[0][i]=drnachvi[i];
}
for(int i=1; i<=N; i++){
for(int j=1; j<i; j++){
if(bati[i][j]==1){
pair<int,int>p={i,j};
if(mp[p]==0){
int maomao=-1;
for(int juuu=0; juuu<batiii; juuu++){
if(drnachvi[juuu]==j){
maomao=juuu;
break;
}
}
if(maomao!=-1){
maomao++;
for(int ka=0; ka<batiii; ka++){
if(ans[ka][maomao]==-19){
ans[ka][maomao]=i;
ans[ka][maomao-1]=j;
if(ka<batiii-1){
ans[ka+1][maomao]=j;
ans[ka+1][maomao-1]=j;
}
break;
}
}
}
mp[p]=1;
}
}
}
}
for(int i=0; i<batiii; i++){
for(int j=0; j<batiii; j++){
if(ans[i][j]==-19){
if(i==0){
if(j>0)ans[i][j]=ans[i][j-1];
else ans[i][j]=1;
}
else ans[i][j]=ans[i-1][j];
}
}
}
// if(ans.size()>2){
// vector<vector<int>>ixvi(ans.size()-2, vector<int>(ans.size()-2));
// for(int i=0; i<ans.size()-2; i++){
// for(int j=0; j<ans.size()-2; j++){
// ixvi[i][j]=ans[i][j];
// }
// }
// return ixvi;
// }
// else return ans;
return ans;
}
}
