Problem

A graph is given in which N vertices, each numbered from 1 to N, are connected by N-1 undirected edges. For each vertex, output the shortest number of steps to start from that vertex and visit all vertices.

However, one step is to follow one side from one vertex and move to another vertex.

Constraints

* 2 ≤ N ≤ 105
* 1 ≤ ui, vi ≤ N (1 ≤ i ≤ N-1)
* ui ≠ vi
* The graph given is concatenated

Input

The input is given in the following format.


N
u1 v1
..
..
..
uN−1 vN−1


The first line is given one integer N.
In the following N-1 line, the integers ui and vi representing the vertex numbers at both ends of the i-th side are given on the i-th line, separated by blanks.

Output

Output the shortest number of steps to visit all vertices starting from vertex i on the i-th line from vertex 1 to vertex N.

Examples

Input

2
1 2


Output

1
1


Input

6
1 2
1 3
3 4
3 5
5 6


Output

7
6
8
7
7
6
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,b) FOR(i,0,b)
#define PB push_back
#define ALL(c) c.begin(),c.end()
#define cat //cout << __LINE__ << endl;
using namespace std;
typedef int LL;
typedef int ut;
typedef pair<ut,ut> pr;
typedef vector<ut> VI;
typedef vector<pr> Vpr;
typedef priority_queue<pr,Vpr,greater<pr> > PQ;
const int SIZE=2*1e5;
//const ut INF=1LL<<60;
VI edge[SIZE];
bool dead[SIZE];
LL ans[SIZE];
bool searched[SIZE];
int needs[SIZE];
int grav[SIZE];
int dist[SIZE];
//int nums[SIZE];
//int sums[SIZE];
int times[SIZE];
int depthest[SIZE];
int timer;
Vpr depters[SIZE];
int depther[SIZE];
LL dfs(int start,int bad,VI& nodes,int depth,bool want){
	int ans=0;
	queue<pr> st;
	st.push(pr(start,bad)); 
	depther[start]=depth;
	while(!st.empty()){
		int now=st.front().first,from=st.front().second;
		st.pop();
		if(dead[now]){
			if(from!=depters[now][0].second)  ans=max(ans,depters[now][0].first+depther[now]);
			else  ans=max(ans,depters[now][1].first+depther[now]);
			continue;
		}
		timer++;
		if(want)
			nodes.PB(now);
		//cout << now << " " << depth << endl;
		ans=max(ans,depther[now]);
		REP(i,edge[now].size()){
			int next=edge[now][i];
			if(next!=from){
				depther[next]=depther[now]+1;
				st.push(pr(next,now));
			}
		}
	}
	//cout << start <<" " << ans << endl;
	return ans;
}
/*
void gives(int now,int from,int depth,LL alls,LL nodes){
	ans[now]+=depth*nodes+alls;
	REP(i,edge[now].size()){
		int next=edge[now][i];
		if(next!=from && !dead[next])
			gives(next,now,depth+1,alls,nodes);
	}
}*/
void centerize(int now,VI& nodes){
	cat;
	dead[now]=true;
	VI dummy;
//	LL alls=0;
	//cout << now;
	REP(i,edge[now].size()){
		timer=0;
		int next=edge[now][i];
		//if(dead[next]) continue;
		depters[now].PB(pr(dfs(next,now,dummy,1,false),next));
	//	cout << depters[now].back().first;
//		nums[i]=timer;
//		alls+=sums[i];
	}
	dummy.clear();
	//cout << endl;
	depters[now].PB(pr(0,-1));
	sort(ALL(depters[now]),greater<pr>());
//	ans[now]+=alls;
//	REP(i,edge[now].size()){
//		int next=edge[now][i];
//		if(dead[next]) continue;
//		gives(next,now,1,alls-sums[i],nodes.size()-nums[i]);
//		alls+=sums[i];
//	}
	cat;	
}

void solve(int now){
	//cout << now << endl;
	cat;
	VI nodes;
	PQ qu;
	dfs(now,-1,nodes,1,true);
	cat;
	int last=nodes[0];
	cat;
	cat;
	REP(i,nodes.size()){
		needs[nodes[i]]=-1;
		searched[nodes[i]]=false;
		grav[nodes[i]]=0;
		times[nodes[i]]=0;
		REP(j,edge[nodes[i]].size()){
			int next=edge[nodes[i]][j];
			if(!dead[next]) needs[nodes[i]]++;
		}

		if(needs[nodes[i]]==0) qu.push(pr(0,nodes[i]));
	}
	cat;
	while(!qu.empty()){
		int now=qu.top().second,gravity=qu.top().first;
		//cout << gravity <<" " << now <<" " <<endl;
		qu.pop();
		searched[now]=true;
		last=now;
		REP(i,edge[now].size()){
			int next=edge[now][i];
			if(dead[next]) continue;
			if(searched[next]) continue;
			grav[next]+=grav[now]+1;
			times[next]++;
			if(times[next]==needs[next]) qu.push(pr(grav[next],next));
		}

	}
	centerize(last,nodes);
	nodes.clear();
//	cout << last << endl;
	REP(i,edge[last].size()){
		int next=edge[last][i];
		if(dead[next]) continue;
		solve(next);
	}
}
int main(){
	int N,u,v;
	cin >> N;
	REP(i,N-1){
		scanf("%d %d",&u,&v);
		edge[v].PB(u);
		edge[u].PB(v);
	}
	solve(1);
	FOR(i,1,N+1){
		printf("%d\n",N*2-2-depters[i][0].first);
	}
	return 0;
}