//testing Ai code
// Strategy: Find a DFS tree and build a 3N grid with optimizations:
// - Don't return after reaching the deepest node
// - Only create an extra line for backedges if they go downward
#include "worldmap.h"
#include <vector>
#include <iostream>
#define debug
using namespace std;
#define maxn 120
int longest[maxn];
int tin[maxn];
int vis[maxn];
int prof[maxn];
vector<int> add[maxn];
vector<vector<int> > G,T;
vector<vector<int> > ans;
int K;
int cnt;
int up;
int mxp;
int leaves;
int endpoint;
// DFS to build spanning tree and find longest path
pair<int,int> dfs(int vx,int par=-1){
debug("dfs %d\n",vx);
vis[vx] = 1;
tin[vx] = cnt++;
int depth = 0;
pair<int,int> res ({0,vx});
for(int viz : G[vx]){
if(!vis[viz]){
T[vx].push_back(viz);
prof[viz] = 1 + prof[vx];
auto u = dfs(viz,vx);
if(u.first+1 > res.first){
res.first = u.first+1;
longest[vx] = viz;
res.second = u.second;
}
}
else if(tin[viz] > tin[vx]){
// Backedge going down
add[vx].push_back(viz);
}
}
return res;
}
int N;
// Add tree edge to the grid
void add_edge(int a,int b){
debug("add %d %d\n",a,b);
if(K == 0){
for(int i=0;i<3*N;i++)
ans[0][i] = (i%2) ? a : b;
K++;
return;
}
if(ans[K-1][0] == b || ans[K-1][1] == b)
swap(a,b);
if(ans[K-1][0] == a)
swap(a,b);
for(int i=0;i<3*N;i++)
ans[K][i] = (i%2) ? b : a;
K++;
}
// Add backedges (non-tree edges)
void add_adj(int vx){
if(K == 0){
int t = 0;
for(int i=0;i<3*N;i++){
if(i%2 == 0 && t < add[vx].size()){
ans[K][i] = add[vx][t];
up = max(up, i+1);
t++;
}
else
ans[K][i] = vx;
}
K++;
return;
}
int t = 0;
for(int i=0;i<3*N;i++){
if(ans[K-1][i] == vx && t < add[vx].size()){
ans[K][i] = add[vx][t];
up = max(up, i+1);
t++;
}
else
ans[K][i] = vx;
}
K++;
}
int stop;
// Build the grid by traversing the tree
void dfs2(int vx,int ret){
up = max(up,2);
if(T[vx].size() == 0) {
leaves++;
if(vx == endpoint){
debug("!stop\n");
stop = 1;
}
return;
}
debug("dfs2 %d longest %d list :",vx,longest[vx]);
for(int a : T[vx]) debug("%d ",a);
debug("\n");
// Add backedges if any
if(add[vx].size())
add_adj(vx);
// Process non-longest children first
for(int viz : T[vx])
if(viz != longest[vx]){
add_edge(vx,viz);
dfs2(viz,ret);
if(!stop)
add_edge(vx,viz);
}
// Process longest child (optimization: don't return from deepest path)
add_edge(vx,longest[vx]);
debug("oi");
dfs2(longest[vx],0);
if(!stop && T[longest[vx]].size() > 0)
add_edge(vx,longest[vx]);
}
std::vector<std::vector<int> > create_map(int _N, int M, std::vector<int> A, std::vector<int> B) {
// Initialization
N = _N;
if(N == 1){
ans = vector<vector<int> > (1, vector<int>(1));
ans[0][0] = 1;
return ans;
}
G = vector<vector<int> > (N);
T = vector<vector<int> > (N);
ans = vector<vector<int> > (3*N, vector<int>(3*N));
cnt = K = up = mxp = stop = leaves = 0;
// Build adjacency list
for (int i = 0; i < M; i++) {
A[i]--;
B[i]--;
G[A[i]].push_back(B[i]);
G[B[i]].push_back(A[i]);
}
for(int i=0;i<N;i++){
vis[i] = 0;
add[i].clear();
}
debug("ok\n");
// Find spanning tree and longest path endpoint
endpoint = dfs(0).second;
debug("ok2\n");
// Build the grid
dfs2(0,1);
debug("ok3\n");
debug("diam %d, leaves %d\n",mxp,leaves);
// Convert to 1-indexed
for (int i = 0; i < int(ans.size()); i++) {
for (int j = 0; j < int(ans.size()); j++) {
ans[i][j]++;
}
}
// Fill remaining rows
for(int i=K;i<3*N;i++)
for(int j=0;j<3*N;j++)
ans[i][j] = ans[i-1][j];
K = max(K,up);
// Create final result with correct size
vector<vector<int> > ret (K, vector<int>(K));
for(int i=0;i<K;i++)
for(int j=0;j<K;j++)
ret[i][j] = ans[i][j];
return ret;
}
