跑一遍 dijkstra，再从大到小将值加入两个集合。
加入的规则是：贪心，尽量让两个集合的差距小

#include<bits/stdc++.h>
#define int long long
using namespace std;

struct node{
	int val,next,to;
}edg[1000005];
int elen;
struct point{
	int ans,x;
	bool operator < (const point &A)const{
		return ans>A.ans;
	}
};

priority_queue<point> q;
point ans2[1000003];
int n,m,s;
int x,y,z;
int ans[1000005];
bool vis[1000005];
bool col[1000003];
int head[1000005];
int sum;

void add(int u,int v,int val){
	elen++;
	edg[elen].to=v;
	edg[elen].val=val;
	edg[elen].next=head[u];
	head[u]=elen;
	
}

signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)ans[i]=1e18; 
	for(int i=1;i<n;i++){
		scanf("%lld%lld",&x,&y);
		add(x,y,1);
	}
	
	ans[1]=0;
	q.push({0,1});
	while(!q.empty()){
		x=q.top().x;
		q.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(int i=head[x];i;i=edg[i].next){
			int to=edg[i].to;
			int cost=edg[i].val;
			if(ans[to]>ans[x]+cost){
				ans[to]=ans[x]+cost;
				q.push({ans[to],to});
			}
		}
	}
	for(int i=1;i<=n;i++){
		sum+=ans[i]+1;
		ans2[i].ans=ans[i]+1;
		ans2[i].x=i;
//		cout<<ans[i]+1<<endl;
	}
	sort(ans2+1,ans2+1+n);
	if(sum&1)puts("-1");
	else{
		sum=0;
		for(int i=1;i<=n;i++){
			if(sum<0){
				sum+=ans2[i].ans;
				col[ans2[i].x]=1;
			}
			else sum-=ans2[i].ans;
//			printf("%lld ",ans2[i].ans);
		}
		if(sum==0)for(int i=1;i<=n;i++)printf("%d ",col[i]);
		else puts("-1");
	}
	return 0;
}