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>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define INF 1000000000
#define mod 1000000007
using ll=long long;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

template<typename T>
struct rerooting{
    using F=function<T(T,int)>;//集合，頂点番号
    using M=function<T(T,T)>;

    int V;
    vector<vector<int>> G;
    vector<vector<T>> dp;
    vector<T> ans;
    // dp_v = g(merge(f(dp_c1,c1),...,f(dp_ck,ck)),v)
    F f,g;  // TxN->T
    M merge;// TxT->T，子を集約する関数，モノイド
    T gen;
    //gen: mergeの元
    rerooting(int V,F f,M merge,T gen,F g=[](T a,int b){return a;})
        :V(V),f(f),merge(merge),gen(gen),g(g),G(V),dp(V),ans(V,gen){}
    
    //bidirectional
    void add_edge(int a,int b){
        G[a].push_back(b);
        G[b].push_back(a);
    }
    T dfs1(int pre,int now){
        T ret=gen;
        for(int i=0;i<G[now].size();i++)if(G[now][i]!=pre){
            dp[now][i]=dfs1(now,G[now][i]);
            ret=merge(ret,f(dp[now][i],G[now][i]));
        }
        return g(ret,now);
    }
    void dfs2(int pre,int now,T frompar){
        for(int i=0;i<G[now].size();i++){
            if(G[now][i]==pre){
                dp[now][i]=frompar;
                break;
            }
        }
        vector<T> lsum(G[now].size()+1),rsum(G[now].size()+1);//親も混ぜて累積
        lsum[0]=gen;rsum[G[now].size()]=gen;
        for(int i=0;i<G[now].size();i++) lsum[i+1]=merge(lsum[i],f(dp[now][i],G[now][i]));
        for(int i=G[now].size();i>0;i--) rsum[i-1]=merge(rsum[i],f(dp[now][i-1],G[now][i-1]));
        for(int i=0;i<G[now].size();i++)if(G[now][i]!=pre){
            T fromme=merge(lsum[i],rsum[i+1]);
            dfs2(now,G[now][i],g(fromme,now));
        }
    }
    void build(int root=0){
        for(int i=0;i<V;i++) dp[i].resize(G[i].size());
        dfs1(-1,root);
        dfs2(-1,root,gen);
        for(int i=0;i<V;i++){
            for(int j=0;j<G[i].size();j++) ans[i]=merge(ans[i],f(dp[i][j],G[i][j]));
            ans[i]=g(ans[i],i);
        }
    }
};


signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    auto f=[&](pair<int,int> ch,int v){return make_pair(ch.second-ch.first+1,ch.second+2);};
    auto merge=[&](pair<int,int> l,pair<int,int> r){return make_pair(max(l.first,r.first),l.second+r.second);};
    auto g=[&](pair<int,int> mg,int v){return make_pair(mg.second-mg.first,mg.second);};

    int n;cin>>n;
    rerooting<pair<int,int>> R(n,f,merge,make_pair(0,0),g);
    rep(i,n-1){
        int u,v;cin>>u>>v;u--,v--;
        R.add_edge(u,v);
    }
    R.build();
    rep(i,n)cout<<R.ans[i].first<<endl;
    return 0;
}

