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 rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

typedef int Data;
typedef int SubData;

const int MN=100000;

vector<int> G[MN];
Data dp[MN];			//0-rooted dp[v]=term(merge(dp[u1],dp[u2],...))
SubData dp_nottermed[MN];	//0-rooted merge(dp[u1],...)
Data up[MN];			//up[v]= 0-rooted??§???v?????????p??¨??????, v->p?????????dp?????? term(merge(up[p],dp[v's bro1],dp[v's bro1],...))
Data DP[MN];			//DP[v]: ans for v-rooted tree
vector<SubData> ls,rs;		//ls/rs[i] = 0-rooted??§??????v???children??????/?????????i???merge????????????(???v??§????????????)
SubData init=0;
SubData merge(SubData val,Data v){
	return max(val,v);
}
SubData merge2(SubData x,SubData y){
	return max(x,y);
}
Data term(SubData val){
	return val+1;
}
void dfs(int v,int p=-1){
	SubData val=init;
	for(int u:G[v]) if(u!=p){
		dfs(u,v);
		val=merge(val,dp[u]);
	}
	dp_nottermed[v]=val;
	dp[v]=term(val);
//	cout<<"dp["<<v<<"]="<<dp[v]<<endl;
}
void ufs(int v,int p=-1){		//0-rooted??§upward?????¨???????¨????
	vector<int> ch;	//children
	for(int u:G[v]) if(u!=p) ch.pb(u);
	int K=ch.size();
	ls.resize(K+1);
	rs.resize(K+1);
	ls[0]=init;
	rs[0]=init;
	rep(i,K){
		ls[i+1]=merge(ls[i],dp[ch[i]]);
		rs[i+1]=merge(rs[i],dp[ch[K-1-i]]);
	}
//	if(p==-1) rep1(i,K) show(ls[i]),show(rs[i]);
	rep(i,K){
		int u=ch[i];
		SubData val=merge2(ls[i],rs[K-1-i]);
		if(p>=0) val=merge(val,up[v]);
		up[u]=term(val);
//		cout<<"up["<<u<<"]="<<up[u]<<endl;
	}
	rep(i,K) ufs(ch[i],v);
}
void calcDP(int N,int r=0){
	dfs(r);
//	up[r]=e			//Data????????????(???init)???????????§??¢???????????§??????
	ufs(r);
	rep(v,N){
		SubData val=dp_nottermed[v];
		if(v!=r) val=merge(val,up[v]);
		DP[v]=term(val);
	}
}
int main(){
	int N;
	cin>>N;
	rep(i,N-1){
		int x,y;
		scanf("%d%d",&x,&y);
		x--,y--;
		G[x].pb(y);
		G[y].pb(x);
	}
	calcDP(N);
	rep(i,N) printf("%d\n",(N-1)*2+1-DP[i]);
}