二分图求 hack

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define ps push_back
#define mk make_pair
#define rint register int
#define G cout<<"-------------------"<<endl
inline ll read(){
	char c=getchar();ll x=0,f=1;
	while(!isdigit(c))(c=='-'?f=-1:0),c=getchar();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int N=1e6+10,inf=0x7fffffff;
const ll linf=0x3f7f7f7f7f7f7f7f,mod=1e9+7;
int n,m,ans,anss[N],cnt,hd[N],xuan[N],mac[N],dep[N];
struct jj{
	int fr,to,next;
}bi[N<<1];
pii dui[N];
inline void add(int x,int y){bi[++cnt]={x,y,hd[x]},hd[x]=cnt,bi[++cnt]={y,x,hd[y]},hd[y]=cnt;}
int vis[N],lun;
bool dfs(int x){
	if(!mac[dui[x].fi])return mac[dui[x].fi]=x,xuan[x]=dui[x].fi,1;
	if(!mac[dui[x].se])return mac[dui[x].se]=x,xuan[x]=dui[x].se,1;
	if(vis[dui[x].fi]!=lun){
		vis[dui[x].fi]=lun;
		if(dep[mac[dui[x].fi]]!=dep[x]&&dfs(mac[dui[x].fi]))return mac[dui[x].fi]=x,xuan[x]=dui[x].fi,1;
	}
	if(vis[dui[x].se]!=lun){
		if(dep[mac[dui[x].se]]!=dep[x]&&dfs(mac[dui[x].se]))return mac[dui[x].se]=x,xuan[x]=dui[x].se,1;
	}
	return 0;
}
inline void xly(int x,int fa){
	bool f=0;
	lun=x;
	if(dfs(x))++ans,f=1;
	anss[x]=ans;
	for(int i=hd[x];i;i=bi[i].next){
		int j=bi[i].to;
		if(j==fa)continue;
		xly(j,x);
	}
	if(f)--ans,mac[xuan[x]]=0;
}
inline void sao(int x,int fa){
	dep[x]=dep[fa]+1;
	for(int i=hd[x];i;i=bi[i].next){
		int j=bi[i].to;
		if(!dep[j])sao(j,x);
	}
}
int main(){
	n=read();
	for(int i=1;i<=n;++i)
		dui[i]={read(),read()};
	for(int i=1;i<n;++i)
		add(read(),read());
	sao(1,0);
	xly(1,0);
	for(int i=2;i<=n;++i)
		printf("%d ",anss[i]);
}