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
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
int MOD=1000000007;
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
const int MAX_N=2e5+5;

struct DP {
    lint dp;
    int sub;
    lint far;
    DP(lint dp=0,int sub=0,lint far=0):dp(dp),sub(sub),far(far){}
    DP operator+(const DP& a) const {
        return DP(2*(sub+a.sub)-max(far,a.far),sub+a.sub,max(far,a.far));
    }
    DP addRoot(int W){
        return DP(dp,sub+1,far+W);
    }
};
 
vector<DP> dp[MAX_N];
DP ans[MAX_N];
vector<int> to[MAX_N];
map<pint,int> edleng;

void addedge(int a,int b,int w=1){
    to[a].push_back(b);
    to[b].push_back(a);
    edleng[pint(a,b)]=w;
    edleng[pint(b,a)]=w;
}
 
DP rerootdfs(int v, int p=-1) {
    DP dpSum;
    dp[v] = vector<DP>(to[v].size());
    rep(i,to[v].size()) {
        int u = to[v][i];
        int W=edleng[pint(v,u)];
        if (u == p) continue;
        dp[v][i] = rerootdfs(u,v);
        dpSum = dpSum + dp[v][i];
        }
    return dpSum.addRoot(edleng[pint(v,p)]);
}
void rerootbfs(int v, const DP& dpP=DP(), int p=-1) {
    int deg = to[v].size();
    rep(i,deg) if (to[v][i] == p) dp[v][i] = dpP;
 
    vector<DP> dpLeft(deg+1);
    rep(i,deg) dpLeft[i+1] = dpLeft[i] + dp[v][i];
  
    vector<DP> dpRight(deg+1);
    for (int i = deg-1; i >= 0; --i) dpRight[i] = dpRight[i+1] + dp[v][i];
  
    ans[v] = dpLeft[deg].addRoot(edleng[pint(v,v)]);
 
    rep(i,deg) {
        int u = to[v][i];
        if (u == p) continue;
        DP d = dpLeft[i] + dpRight[i+1];
        rerootbfs(u, d.addRoot(edleng[pint(u,v)]), v);
    }
}

void reroot(){
    rerootdfs(0);
    rerootbfs(0);
}

//デフォルトで部分木のサイズ、最遠距離がついてくる


int main(void){
    int N;
    cin >> N;
    rep(i,N-1){
        int a,b;
        cin >> a >> b;
        a--,b--;
        addedge(a,b);
    }
    reroot();
    rep(i,N) cout << ans[i].dp << endl;
}
