#include "passageconstruction.h"
#include <queue>
#include <vector>
#include <cassert>
#include <numeric>
#include <algorithm>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
const int N=10003,M=5003;
int n,cnt;
int lc[N],rc[N],fa[N],nd[N];
vi vec[N];
void rebuild(int u,int fs){
	int las=u;
	for(int v:vec[u]){
		if(v==fs) continue;
		rebuild(v,u);
		int p=++cnt;
		nd[p]=u;
		fa[lc[p]=v]=p;
		fa[rc[las]=p]=las;
		las=p;
	}
}
bool del[N];
int sz[N],sn[N];
void dfs(int u){
	sz[u]=1;sn[u]=0;
	if(lc[u]&&!del[lc[u]]){
		dfs(lc[u]);sz[u]+=sz[lc[u]];
		if(sz[lc[u]]>sz[sn[u]]) sn[u]=lc[u];
	}
	if(rc[u]&&!del[rc[u]]){
		dfs(rc[u]);sz[u]+=sz[rc[u]];
		if(sz[rc[u]]>sz[sn[u]]) sn[u]=rc[u];
	}
}
vector<int> lis[N];
void proc(int rt,vi cur){
	if(cur.empty()) return;
	int x=rt;
	dfs(rt);
	while(sz[sn[x]]*2>sz[rt]) x=sn[x];
	del[x]=1;
	if(x<=n){
		vi qvec=vec[x];
		if(qvec.size()==1lu) qvec.emplace_back(x);
		if(!cur.empty()){
			vi RES=QueryLCA(cur,qvec,x),out;
			for(int i=0;i<(int)cur.size();++i)
				if(RES[i]) lis[x].emplace_back(cur[i]);
				else out.emplace_back(cur[i]);
			cur.swap(out);
		}
	}
	if(lc[x]){
		vi onin,out,in;
		if(!cur.empty()){
			vi RES=QueryLCA(cur,{nd[x],lc[x]},nd[x]);
			for(int i=0;i<(int)cur.size();++i)
				if(RES[i]) out.emplace_back(cur[i]);
				else onin.emplace_back(cur[i]);
			cur.swap(out);
		}
		if(del[lc[x]]){
			for(int p:onin) lis[x].emplace_back(p);
		}
		else{
			vi in;
			if(!onin.empty()){
				vi RES=QueryLCA(onin,{nd[x],lc[x]},lc[x]);
				for(int i=0;i<(int)onin.size();++i)
					if(RES[i]) in.emplace_back(onin[i]);
					else lis[x].emplace_back(onin[i]);
			}
			proc(lc[x],in);
		}
	}
	if(rc[x]&&!del[rc[x]]){
		vi chain,in,out;
		for(int i=rc[x];i&&!del[i];i=rc[i])
			chain.emplace_back(lc[i]);
		if(chain.size()==1lu) chain.emplace_back(nd[x]);
		vi RES=QueryLCA(cur,chain,nd[x]);
		for(int i=0;i<(int)cur.size();++i)
			if(RES[i]) out.emplace_back(cur[i]);
			else in.emplace_back(cur[i]);
		cur.swap(out);
		proc(rc[x],in);
	}
	if(x!=rt) proc(rt,cur);
}
int d[M][M],p[M][M],q[M];
int mat[N];
int len;
int dl[N],dr[N];
vpii adj[N];
void dfs(int u,int fa,int *dep){
	for(auto [v,w]:adj[u]){
		if(v==fa) continue;
		dep[v]=dep[u]+w;
		dfs(v,u,dep);
	}
}
vpii ConstructPassages(int _N,const vpii &_E){
	n=_N;
	if(n==1) return {{1,2}};
	for(auto [u,v]:_E){
		vec[u].emplace_back(v);
		vec[v].emplace_back(u);
	}
	vi init;
	for(int i=1;i<=n;++i) nd[i]=i,init.emplace_back(i+n);
	cnt=n;
	rebuild(1,0);
	proc(1,init);
	for(int i=n+1;i<=cnt;++i){
		int len=1;
		int u=nd[i],v=lc[i];
		for(int x:lis[i]){
			dl[x]=GetDistance(u,x);
			dr[x]=GetDistance(v,x);
			if(dl[x]==1||dr[x]==1) len=dl[x]+dr[x];
		}
		adj[v].emplace_back(u,len);
		adj[u].emplace_back(v,len);
	}
	for(int i=1;i<=n;++i)
		for(int x:lis[i]){
			d[x-n][i]=GetDistance(i,x);
			dfs(i,0,d[x-n]);
		}
	for(int i=n+1;i<=cnt;++i){
		int u=nd[i],v=lc[i];
		for(int x:lis[i]){
			d[x-n][u]=dl[x];dfs(u,v,d[x-n]);
			d[x-n][v]=dr[x];dfs(v,u,d[x-n]);
		}
	}
	queue<int> que;
	for(int i=1;i<=n;++i){
		iota(p[i]+1,p[i]+n+1,1);
		sort(p[i]+1,p[i]+n+1,[&](int x,int y){return d[i][x]>d[i][y];});
		q[i]=1;mat[i]=0;que.emplace(i);
	}
	int cnt=0;
	while(!que.empty()){
		int u=que.front();que.pop();
		int v=p[u][q[u]];
		if(!mat[v]||d[u][v]<d[mat[v]][v]||(d[u][v]==d[mat[v]][v]&&u<mat[v])){
			if(mat[v]&&++q[mat[v]]<=n) que.emplace(mat[v]);
			mat[v]=u;
		}
		else if(++q[u]<=n) que.emplace(u);
	}
	vpii res;
	for(int i=1;i<=n;++i) res.emplace_back(mat[i]+n,i);
	return res;
}