#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
bool test = false;
void output(vector<vector<int>> A){
for(auto a : A){
for(auto aa : a) cout << aa+1 << " ";
cout << endl;
}
cout << endl;
}
vector<int> BFS(vector<vector<int>> Graph,int start){
int N = Graph.size();
vector<int> ret(N,-1);
queue<int> Q; Q.push(start);
ret.at(start) = 0;
while(Q.size()){
int pos = Q.front(); Q.pop();
for(auto to : Graph.at(pos)) if(ret.at(to) == -1){
ret.at(to) = ret.at(pos)+1;
Q.push(to);
}
}
return ret;
}
vector<pair<char,long long>> RLE(string &s){
if(s.size() == 0) return {};
vector<pair<char,long long>> ret;
char back = s.at(0);
long long streak = 1;
for(int i=1; i<s.size(); i++){
if(back == s.at(i)) streak++;
else{
ret.push_back({back,streak});
back = s.at(i); streak = 1;
}
}
ret.push_back({back,streak});
return ret;
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
for(auto &a : A) a--;
for(auto &b : B) b--;
vector<vector<int>> Graph(N),Tree(N);
for(int i=0; i<M; i++){
int a = i,b = i+1;
a = A.at(i),b = B.at(i);
Graph.at(a).push_back(b);
Graph.at(b).push_back(a);
}
int start = -1;
vector<int> H(N);
{
vector<bool> ok(N);
for(int i=0; i<N; i++) if(Graph.at(i).size()){
auto f = [&](auto f,int pos) -> void {
ok.at(pos) = true;
for(auto to : Graph.at(pos)) if(!ok.at(to)){
Tree.at(pos).push_back(to);
Tree.at(to).push_back(pos);
f(f,to);
}
};
f(f,i);
int D = -1;
for(int p=0; p<N; p++){
auto dist = BFS(Tree,p);
int maxd = *max_element(dist.begin(),dist.end());
if(D < maxd) D = maxd,start = p;
}
auto g = [&](auto g,int pos,int back) -> int {
int ret = 0;
for(auto to : Tree.at(pos)) if(to != back) ret = max(ret,g(g,to,pos));
H.at(pos) = ret;
return ret;
};
g(g,start,-1);
break;
}
}
int K = 240;
int X = 0;
vector<vector<int>> C(K,vector<int>(K,-1));
C.at(0).assign(K,0);
vector<vector<bool>> paint(N,vector<bool>(N)),edge = paint;
for(int i=0; i<M; i++) edge.at(A.at(i)).at(B.at(i)) = true,edge.at(B.at(i)).at(A.at(i)) = true;
vector<bool> already(N);
vector<vector<vector<int>>> Lens(K,vector<vector<int>>(K));
auto dfs = [&](auto dfs,int pos,int back) -> void {
X++;
already.at(pos) = true;
int Y = 0,n = (int)Graph.at(pos).size(),left = n;
vector<bool> posok(n);
for(int i=0; i<n; i++){
int to = Graph.at(pos).at(i);
if(paint.at(pos).at(to)) posok.at(i) = true,left--;
}
for(int i=0; i<n; i++) if(!posok.at(i)){
bool alone = true;
int to = Graph.at(pos).at(i);
for(int k=0; k<n; k++) if(!posok.at(k) && edge.at(to).at(Graph.at(pos).at(k))){
alone = false; break;
}
if(alone){
paint.at(to).at(pos) = true;
paint.at(pos).at(to) = true;
posok.at(i) = true;
C.at(X).at(Y++) = to,C.at(X).at(Y++) = pos;
Lens.at(X).at(1).push_back(Y-2); break;
}
}
if(left && Y == 0) C.at(X).at(Y++) = pos;
for(int i=0; i<n; i++) if(posok.at(i) == false){
posok.at(i) = true;
int to = Graph.at(pos).at(i);
C.at(X).at(Y++) = to;
paint.at(pos).at(to) = true;
paint.at(to).at(pos) = true;
int len = 1;
for(int k=i+1; k<n; k++) if(!posok.at(k) && edge.at(to).at(Graph.at(pos).at(k))){
int to2 = Graph.at(pos).at(k);
C.at(X).at(Y++) = to2;
paint.at(pos).at(to2) = true;
paint.at(to2).at(pos) = true;
paint.at(to).at(to2) = true;
paint.at(to2).at(to) = true;
posok.at(k) = true,len = 2; break;
}
Lens.at(X).at(len).push_back(Y-len);
C.at(X).at(Y++) = pos;
}
for(int i=0; i<n&&Y>0&&Y+2<=2*N; i++) for(int k=i+1; k<n&&Y+2<=2*N; k++){
int to1 = Graph.at(pos).at(i),to2 = Graph.at(pos).at(k);
if(paint.at(to1).at(to2) || !edge.at(to1).at(to2)) continue;
paint.at(to1).at(to2) = true;
paint.at(to2).at(to1) = true;
C.at(X).at(Y++) = to1;
C.at(X).at(Y++) = to2;
int len = 2;
while(Y < 2*N){
bool change = false;
for(int l=0; l<n; l++){
int to3 = Graph.at(pos).at(l);
if(paint.at(to2).at(to3) || !edge.at(to2).at(to3)) continue;
paint.at(to2).at(to3) = true;
paint.at(to3).at(to2) = true;
C.at(X).at(Y++) = to3;
change = true,to2 = to3; break;
}
if(!change) break;
len++;
}
Lens.at(X).at(len).push_back(Y-len);
if(Y < 2*N) C.at(X).at(Y++) = pos;
}
if(Y != 0){
for(; Y<2*N; Y++) C.at(X).at(Y) = pos;
C.at(++X).assign(K,pos);
}
sort(Tree.at(pos).begin(),Tree.at(pos).end(),[&](auto a,auto b){return H.at(a)<H.at(b);});
for(auto to : Tree.at(pos)){
if(to == back) continue;
X++;
for(int i=0; i<K; i++) C.at(X).at(i) = to;
dfs(dfs,to,pos);
for(int i=0; i<K; i++) C.at(X).at(i) = pos;
}
X++;
};
if(start != -1){
C.at(0).assign(K,start);
dfs(dfs,start,-1);
}
K = max(2*N,X);
C.resize(K),Lens.resize(K);
if(K > 2*N) C.erase(C.begin()),K--,Lens.erase(Lens.begin());
for(int i=0; i<K; i++){
C.at(i).resize(K);
if(C.at(i).at(0) == -1) C.at(i).at(0) = C.at(i-1).at(0);
for(int k=1; k<K; k++) if(C.at(i).at(k) == -1) C.at(i).at(k) = C.at(i).at(k-1);
}
while(K > 2*N){
set<int> now(C.back().begin(),C.back().end());
if(now.size() == 1) C.pop_back(),K--,Lens.pop_back();
else break;
}
while(K > 2*N){
bool change = false;
while(K > 2*N){
vector<int> same(K,-1);
for(int i=0; i<K; i++){
for(auto c : C.at(i)){
if(same.at(i) == -1) same.at(i) = c;
else if(same.at(i) != c) same.at(i) = -2;
}
}
bool end = true;
for(int i=0; i<K&&end; i++){
if(same.at(i) == -2) continue;
int r = i;
while(r < K && same.at(r) != -2) r++;
int len = r-i;
for(int k=len-1; k>0; k--){
for(int l=i; l+k<r; l++){
int p1 = same.at(l),p2 = same.at(l+k);
if(p1 == p2){
end = false;
for(int p=l+k; p>l; p--) C.erase(C.begin()+p),K--,Lens.erase(Lens.begin()+p);
break;
}
else if(paint.at(p1).at(p2) && k > 1){
end = false;
for(int p=l+k-1; p>l; p--) C.erase(C.begin()+p),K--,Lens.erase(Lens.begin()+p);
break;
}
}
if(end == false) break;
}
}
if(end) break;
change = true;
}
while(K > 2*N){
vector<int> same(K,-1);
for(int i=0; i<K; i++){
for(int k=0; k<C.at(i).size(); k++){
if(k == 0) same.at(i) = C.at(i).at(k);
else if(same.at(i) != C.at(i).at(k)){same.at(i) = -2; break;}
}
}
for(int i=0; i<K-2; i++){
int s3 = same.at(i+1);
if(s3 == -2) continue;
int s4 = same.at(i+2);
if(s4 == -2) continue;
bool del = true;
for(auto c : C.at(i)) if(edge.at(c).at(s4) == false && c != s4){del = false; break;}
if(del == false) continue;
C.erase(C.begin()+i+1),Lens.erase(Lens.begin()+i+1);
break;
}
if(C.size() == K){
for(int i=0; i<K-1; i++) if(same.at(i) != -2 && same.at(i) == same.at(i+1)){
C.erase(C.begin()+i),Lens.erase(Lens.begin()+i); break;
}
}
if(C.size() == K) break;
K--; change = true;
}
if(change) continue;
while(K > 2*N){
vector<int> same(K,-1);
for(int i=0; i<K; i++){
for(int k=0; k<C.at(i).size(); k++){
if(k == 0) same.at(i) = C.at(i).at(k);
else if(same.at(i) != C.at(i).at(k)){same.at(i) = -2; break;}
}
}
bool end = true;
for(X=3; X<K; X++){
if(same.at(X-2) == -2 || same.at(X-1) == -2) continue;
auto Len = Lens.at(X);
bool zero = true;
for(auto l : Len) if(l.size()){zero = false; break;}
if(zero) continue;
string s(2*N,'x');
for(int i=1; i<2*N-1; i++) if(C.at(X-3).at(i) == C.at(X-2).at(i)) s.at(i) = 'o';
//cout << X+1 << " " << s << endl;
//for(int i=0; i<2*N; i++) cout << C.at(X-3).at(i) << " "; cout << endl;
//for(int i=0; i<2*N; i++) cout << C.at(X-2).at(i) << " "; cout << endl;
//for(int i=0; i<2*N; i++) cout << C.at(X-1).at(i) << " "; cout << endl;
//for(int i=0; i<2*N; i++) cout << C.at(X).at(i) << " "; cout << endl;
auto S = RLE(s);
int leader = C.at(X-1).at(0);
vector<int> move(K,leader);
vector<pair<int,int>> space;
int p = 0;
for(auto [c,len] : S){
if(c == 'o') space.push_back({len,p});
p += len;
}
sort(space.begin(),space.end());
int l = 1;
for(auto [len,p] : space){
while(len >= l && l < K){
if(Len.at(l).size() == 0){l++; continue;}
int s = Len.at(l).back(); Len.at(l).pop_back();
for(int q=s; q<s+l; q++) move.at(p++) = C.at(X).at(q);
len -= l;
if(len) len--,p++;
}
while(l < K && Len.at(l).size() == 0) l++;
if(l == K) break;
}
if(l == K){
end = false;
for(int i=0; i<2*N; i++){
if(move.at(i) != leader) C.at(X-1).at(i) = move.at(i),C.at(X-2).at(i) = leader;
}
C.erase(C.begin()+X),Lens.erase(Lens.begin()+X);
break;
}
}
if(end) break;
change = true;
K--; break;
}
if(change == false) break;
}
if(K > 2*N) for(auto &c : C) c.resize(2*N);
while(K > 2*N){
bool change = false;
while(K > 2*N && false){
vector<int> same(K,-1);
for(int i=0; i<K; i++){
for(auto c : C.at(i)){
if(same.at(i) == -1) same.at(i) = c;
else if(same.at(i) != c) same.at(i) = -2;
}
}
bool end = true;
for(int i=0; i<K&&end; i++){
if(same.at(i) == -2) continue;
int r = i;
while(r < K && same.at(r) != -2) r++;
int len = r-i;
for(int k=len-1; k>0; k--){
for(int l=i; l+k<r; l++){
int p1 = same.at(l),p2 = same.at(l+k);
if(p1 == p2){
end = false;
for(int p=l+k; p>l; p--) C.erase(C.begin()+p),K--,Lens.erase(Lens.begin()+p);
break;
}
else if(paint.at(p1).at(p2) && k > 1){
end = false;
for(int p=l+k-1; p>l; p--) C.erase(C.begin()+p),K--,Lens.erase(Lens.begin()+p);
break;
}
}
if(end == false) break;
}
}
if(end) break;
change = true;
}
while(K > 2*N){
vector<int> same(K,-1);
for(int i=0; i<K; i++){
for(int k=0; k<C.at(i).size(); k++){
if(k == 0) same.at(i) = C.at(i).at(k);
else if(same.at(i) != C.at(i).at(k)){same.at(i) = -2; break;}
}
}
for(int i=0; i<K-2; i++){
int s3 = same.at(i+1);
if(s3 == -2) continue;
int s4 = same.at(i+2);
if(s4 == -2) continue;
bool del = true;
for(auto c : C.at(i)) if(edge.at(c).at(s4) == false && c != s4){del = false; break;}
if(del == false) continue;
C.erase(C.begin()+i+1),Lens.erase(Lens.begin()+i+1);
break;
}
if(C.size() == K){
for(int i=0; i<K-1; i++) if(same.at(i) != -2 && same.at(i) == same.at(i+1)){
C.erase(C.begin()+i),Lens.erase(Lens.begin()+i); break;
}
}
if(C.size() == K) break;
K--; change = true;
}
if(change) continue;
//output(C);
for(int i=K-1; i>=0; i--){
if(i) for(int k=0; k<2*N; k++){
int c = C.at(i).at(k),c2 = c,c3 = c,c4 = c;
if(k) c2 = C.at(i).at(k-1);
if(k < 2*N-1) c3 = C.at(i).at(k+1);
if(i+1 < K) c4 = C.at(i+1).at(k);
if(c == c2 && c2 == c3 && c3 == c4){
int d = C.at(i-1).at(k),d2 = d,d3 = d,d4 = d;
if(k) d2 = C.at(i-1).at(k-1);
if(k < 2*N-1) d3 = C.at(i-1).at(k+1);
if(i-1) d4 = C.at(i-2).at(k);
if(d == d2 && d2 == d3 && d3 == d4) C.at(i-1).at(k) = c;
}
}
if(i) for(int k=2*N-1; k>=0; k--){
int c = C.at(i).at(k),c2 = c,c3 = c,c4 = c;
if(k) c2 = C.at(i).at(k-1);
if(k < 2*N-1) c3 = C.at(i).at(k+1);
if(i+1 < K) c4 = C.at(i+1).at(k);
if(c == c2 && c2 == c3 && c3 == c4){
int d = C.at(i-1).at(k),d2 = d,d3 = d,d4 = d;
if(k) d2 = C.at(i-1).at(k-1);
if(k < 2*N-1) d3 = C.at(i-1).at(k+1);
if(i-1) d4 = C.at(i-2).at(k);
if(d == d2 && d2 == d3 && d3 == d4) C.at(i-1).at(k) = c;
}
}
if(i < K-1) for(int k=0; k<2*N; k++){
int c = C.at(i+1).at(k),d = C.at(i).at(k);
if(c == d) continue;
int d2 = c,d3 = c,d4 = d;
if(k) d2 = C.at(i).at(k-1);
if(k < 2*N-1) d3 = C.at(i).at(k+1);
if(i) d4 = C.at(i-1).at(k);
if(d != d4) continue;
if(d2 == c || d2 == d){
if(d3 == c || d3 == d){
if(i || d2 == d || d3 == d) C.at(i).at(k) = C.at(i+1).at(k);
}
}
}
if(i < K-1) for(int k=2*N-1; k>=0; k--){
int c = C.at(i+1).at(k),d = C.at(i).at(k);
if(c == d) continue;
int d2 = c,d3 = c,d4 = d;
if(k) d2 = C.at(i).at(k-1);
if(k < 2*N-1) d3 = C.at(i).at(k+1);
if(i) d4 = C.at(i-1).at(k);
if(d != d4) continue;
if(d2 == c || d2 == d){
if(d3 == c || d3 == d){
if(i || d2 == d || d3 == d) C.at(i).at(k) = C.at(i+1).at(k);
}
}
}
}
vector<vector<int>> near(N,vector<int>(N));
for(int i=0; i<K; i++) for(int k=0; k<2*N; k++){
if(i+1 < K){
int c = C.at(i).at(k);
int c2 = C.at(i+1).at(k);
near.at(c).at(c2)++;
near.at(c2).at(c)++;
}
if(k+1 < 2*N){
int c = C.at(i).at(k);
int c2 = C.at(i).at(k+1);
near.at(c).at(c2)++;
near.at(c2).at(c)++;
}
}
for(int i=K-1; i>=0; i--) for(int k=2*N; k--;){
int c = C.at(i).at(k),c2 = -1,c3 = -1,c4 = -1,c5 = -1;
int ne = 0;
if(i) c2 = C.at(i-1).at(k),ne++;
if(k) c3 = C.at(i).at(k-1),ne++;
if(k < 2*N-1) c4 = C.at(i).at(k+1),ne++;
if(i+1 < K) c5 = C.at(i+1).at(k),ne++;
if(c3 == -1) c3 = c2;
if(c4 == -1) c4 = c3;
if(c5 == -1) c5 = c4;
if(c4 == -1) c4 = c5;
if(c3 == -1) c3 = c4;
if(c2 == -1) c2 = c3;
if(c2 == c3 && c3 == c4 && c4 == c5 && c != c2 && near.at(c).at(c2) > ne){
C.at(i).at(k) = c2; near.at(c).at(c2) -= ne,near.at(c2).at(c) -= ne;
break;
}
}
//output(C);
for(int i=K-1; i>0&&K>2*N; i--) if(C.at(i) == C.at(i-1)){C.erase(C.begin()+i),K--;}
//output(C);
}
K = max(2*N,K); Lens.clear();
while(C.size() < K) C.push_back(vector<int>(K,-1));
for(int i=0; i<K; i++){
C.at(i).resize(K);
if(C.at(i).at(0) == -1){
for(int k=0; k<N; k++){
bool ok = true;
for(auto c : C.at(i-1)) if(edge.at(c-1).at(k) == false && c-1 != k){ok = false; break;}
if(ok){C.at(i).at(0) = k; break;}
}
}
for(int k=1; k<K; k++) if(C.at(i).at(k) == -1) C.at(i).at(k) = C.at(i).at(k-1);
for(auto &c : C.at(i)) c++;
}
for(auto &c : C) while(c.size() > K) c.pop_back();
set<pair<int,int>> UV,AB;
for(int i=0; i<M; i++) AB.insert({min(A.at(i),B.at(i)),max(A.at(i),B.at(i))});
for(int i=0; i<K; i++) for(int k=0; k<K; k++){
int c = C.at(i).at(k);
if(k+1 < K){
int c2 = C.at(i).at(k+1);
UV.insert({min(c,c2)-1,max(c,c2)-1});
}
if(i+1 < K){
int c2 = C.at(i+1).at(k);
UV.insert({min(c,c2)-1,max(c,c2)-1});
}
}
for(int i=0; i<N; i++) if(UV.count({i,i})) UV.erase({i,i});
if(AB != UV){
cout << "You" << endl;
for(auto [u,v] : UV) cout << u+1 << " " << v+1 << endl;
cout << "AB" << endl;
for(auto [u,v] : AB) cout << u+1 << " " << v+1 << endl;
}
return C;
}
