#include "worldmap.h"
#include<bits/stdc++.h>
using namespace std;
void dfs(int x, vector<vector<int>> &AR, vector<int> &pos, vector<vector<int>> &adj, vector<int> &order, int &buff)
{
pos[x] = buff++;
order.push_back(x);
for (int i=0; i<AR[x].size(); i++)
{
if (pos[AR[x][i]]!=-1)
{
adj[AR[x][i]][x] = 1;
continue;
}
dfs(AR[x][i], AR, pos, adj, order, buff);
order.push_back(x);
}
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
vector<vector<int>> ans(2 * N, vector<int>(2 * N, 1));
vector<vector<int>> AR(N), adj(N, vector<int>(N,0));
vector<int> order, pos(N, -1);
for (int i=0; i<M; i++)
{
AR[A[i]-1].push_back(B[i]-1);
AR[B[i]-1].push_back(A[i]-1);
}
int buff=0;
dfs(0, AR, pos, adj, order, buff);
vector<int> S;
for (int i=0; i<order.size(); i++)
{
if (S.size()<2 || S[S.size()-2]!=order[i])
S.push_back(order[i]);
else
S.pop_back();
for (int j=0; j<2*N; j++)ans[i][j] = S.back()+1;
for (int j=0; j<S.size(); j++)
{
ans[i][2*j] = S[j]+1;
ans[i][2*j+1] = S[j]+1;
}
for (int j=0; j<S.size(); j++)
{
if (adj[S[j]][S.back()])
{
ans[i][2*j+1]=S.back()+1;
ans[i][2*j+2]=S[j]+1;
}
}
}
return ans;
}
