#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
bool shift = false;
vector<int> gaps(int N, int color, bool shift) {
vector<int> ret(3 * N, -1);
for(int i = shift; i < 3 * N; i += 2) {
ret[i] = color;
}
return ret;
}
void tree(int N, int M, int color, vector<bool>& visited, vector<vector<int>>& ans, vector<vector<int>>& edges) {
visited[color] = true;
shift = !shift;
vector<int> current(3 * N, color);
int ix = shift;
ans.push_back(gaps(N, color, shift));
for(int e : edges[color]) {
current[ix] = e;
ix += 2;
}
ans.push_back(current);
ans.push_back(gaps(N, color, shift));
for(int e : edges[color]) {
if(visited[e]) continue;
tree(N, M, e, visited, ans, edges);
}
ans.push_back(gaps(N, color, !shift));
ans.push_back(gaps(N, color, shift));
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
vector<vector<int>> ans;
vector<vector<int>> edges(N + 1);
vector<bool> visited(N + 1, false);
for(int i = 0; i < M; i++) {
edges[A[i]].push_back(B[i]);
edges[B[i]].push_back(A[i]);
}
tree(N, M, 1, visited, ans, edges);
vector<vector<int>> ans2;
for(int i = 1; i < ans.size() - 1; i++) {
ans2.push_back(ans[i]);
if(ans[i][0] == -1) {
for(int j = 0; j < 3 * N; j += 2) {
ans2.back()[j] = ans[i + 1][j];
}
i++;
}
else if(ans[i][1] == -1) {
for(int j = 1; j < 3 * N; j += 2) {
ans2.back()[j] = ans[i + 1][j];
}
i++;
}
}
while(ans2.size() < 3 * N) {
ans2.push_back(vector<int>(3 * N, 1));
}
return ans2;
}
