//#include "worldmap.h"
#include<bits/stdc++.h>
using namespace std;
struct Graph {
int n; // 節點數
int m_cap; // 最多能存的「有向邊」數 (無向圖要給 2*M)
vector<int> head; // head[u] = 第一條出邊的 idx，-1 代表空
vector<int> to, nxt; // forward-star
int idx; // 當前可用邊索引
vector<char> vis; // 拜訪標記 (0/1)
vector<int> dfs_path; // Euler 路徑
/* 建構子：n 節點，m_cap = 2*M (若無向) 或 M (若有向) */
Graph(int _n, int _max_edges)
: n(_n), m_cap(_max_edges), head(_n + 1, -1),
to(_max_edges), nxt(_max_edges), idx(0),
vis(_n + 1, 0) {}
/* 在鄰接串列前插入 (u→v) */
void add_directed(int u, int v) {
to[idx] = v;
nxt[idx] = head[u];
head[u] = idx;
++idx;
}
/* 無向圖：各插一次 */
void add_edge(int u, int v) {
add_directed(u, v);
add_directed(v, u);
}
/* DFS（Euler 路徑：進入 push，回溯再 push 原點） */
void dfs(int u) {
vis[u] = 1;
dfs_path.push_back(u);
for (int e = head[u]; e != -1; e = nxt[e]) {
int v = to[e];
if (!vis[v]) {
dfs(v);
dfs_path.push_back(u); // 回溯
}
}
}
/* 取得 DFS Euler 路徑；未連通也能處理 */
vector<int> get_dfs_path(int root = 1) {
fill(vis.begin(), vis.end(), 0);
dfs_path.clear();
dfs(root);
for (int u = 1; u <= n; ++u) // 若圖有多連通塊
if (!vis[u]) dfs(u); // 依序補 DFS
return dfs_path;
}
/* 回傳 u 的鄰居 (複製一份 vector) */
vector<int> get_neighbors(int u) const {
vector<int> nbrs;
for (int e = head[u]; e != -1; e = nxt[e])
nbrs.push_back(to[e]);
return nbrs;
}
};
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
Graph g(N,2*M);
for(int i=0;i<M;i++){
g.add_edge(A[i],B[i]);
}
auto path = g.get_dfs_path(1);
vector<vector<int>> ans(6*N-3, vector<int>(6*N-3, 1));
for(int i=0;i<2*N-1;i++){
for(int j=0;j<6*N-3;j++){
ans[3*i][j] = path[i];
}
auto ed = g.get_neighbors(path[i]);
int ct = 0;
for(int j:ed){
ans[3*i+1][ct] = j;
ans[3*i+1][ct+1] = path[i];
ct+=2;
}
for(int j=ct;j<6*N-3;j++) ans[3*i+1][j] = path[i];
for(int j=0;j<6*N-3;j++) ans[3*i+2][j] = path[i];
}
return ans;
}
