#include<bits/stdc++.h>
#include "incursion.h"
using namespace std;
#define fall(i,a,n) for(int i=a;i<=n;i++)
#define rfall(i,a,n) for(int i=a;i>=n;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
int n=sz(F)+1;
vector<vector<int>> g(n);
for(auto [u,j]:F){
u--,j--;
g[u].pb(j); g[j].pb(u);
}
vector<int> ans(n),p(n,-1),dp(n),mark(n),par(n,-1),cs;
auto dfs1=[&](auto &&self,int x)->void{
dp[x]=1;
for(auto u:g[x]) if(u!=p[x]){
p[u]=x;
self(self,u);
dp[x]+=dp[u];
}
};
auto get_centroid=[&](auto &&self,int x)->int{
for(auto u:g[x]) if(u!=p[x] && 2*dp[u]>n) return self(self,u);
cs.pb(x);
for(auto u:g[x]) if(u!=p[x] && 2*dp[u]==n) cs.pb(u);
return x;
};
auto dfs2=[&](auto &&self,int x)->void{
for(auto u:g[x]) if(u!=par[x]){
par[u]=x;
self(self,u);
}
};
auto dfs=[&](auto &&self,int x)->void{
mark[x]=1;
for(auto u:g[x]) if(!mark[u]){
ans[u]=1;
if(u==par[x]) ans[u]=0;
if(sz(cs)==2 && u==cs[0] && x==cs[1]) ans[u]=1;
self(self,u);
}
};
safe--;
dfs1(dfs1,0);
int centroid=get_centroid(get_centroid,0);
fall(i,0,n-1) cout<<dp[i]<<" ";
cout<<"\n";
cout<<sz(cs)<<"\n";
for(auto x:cs) cout<<x<<" ";
cout<<"\n";
dfs2(dfs2,centroid);
dfs(dfs,safe);
return ans;
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
int n=sz(F)+1;
vector<vector<int>> g(n),child(n);
for(auto [u,j]:F){
u--,j--;
g[u].pb(j),g[j].pb(u);
}
vector<int> p(n),dp(n),par(n,-1);
auto dfs1=[&](auto &&self,int x)->void{
dp[x]=1;
for(auto u:g[x]) if(u!=p[x]){
p[u]=x;
self(self,u);
dp[x]+=dp[u];
}
};
vector<int> cs;
auto get_centroid=[&](auto &&self,int x)->int{
for(auto u:g[x]) if(u!=p[x] && 2*dp[u]>n) return self(self,u);
for(auto u:g[x]) if(u!=p[x] && 2*dp[u]==n) cs.pb(u);
return x;
};
auto dfs=[&](auto &&self,int x)->void{
dp[x]=1;
for(auto u:g[x]) if(u!=par[x]){
par[u]=x;
if(sz(cs)==1 || u!=cs[0])child[x].pb(u);
self(self,u);
dp[x]+=dp[u];
}
sort(all(child[x]),[&](int a,int b){
return dp[a]>dp[b];
});
};
dfs1(dfs1,0);
int centroid=get_centroid(get_centroid,0); cs.pb(centroid);
dfs(dfs,centroid);
if(sz(cs)==2) par[cs[0]]=cs[1],par[cs[1]]=cs[0];
vector<int> vals(n,-1),mark(n); curr--; vals[curr]=t;
while(true){
if(sz(cs)==1 || (curr!=cs[0] && curr!=cs[1])){
if(vals[curr]==1){
cout<<curr<<" "<<"oieee\n";
curr=par[curr];
vals[curr]=visit(curr+1);
continue;
}
bool ok=0;
for(auto u:child[curr]){
if(vals[u]!=-1)continue;
vals[u]=visit(u+1);
if(vals[u]!=1){
curr=u;
ok=1;
break;
}
visit(curr+1);
}
if(!ok) return;
}
if(vals[curr]==1){
for(auto x:cs) if(x!=curr){
vals[x]=visit(x+1);
curr=x;
break;
}
continue;
}
bool ok=0;
for(auto u:child[curr]){
if(vals[u]!=-1) continue;
vals[u]=visit(u+1);
if(vals[u]!=1){
curr=u;
ok=1;
break;
}
visit(curr+1);
}
if(!ok)return;
}
}
