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
// https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2016Day2/problems/I
// #include"../ReRooting.cpp"
#include<vector>
#include<iostream>
namespace ProconLib{

    template<typename edge_t>
    class StructInterface{
        struct data_t;    
        struct value_t;
        data_t E();
        data_t merge(data_t x,data_t y);
        data_t mergeV(data_t x,int v);
        data_t mergeE(data_t x,const edge_t& e);
        value_t solve(int v,const std::vector<data_t>& vec);
    };

    template<class graph_t,class Struct>
    class ReRooting{
        int N;
        int root;
        Struct st;
        using data_t=typename Struct::data_t;
        using value_t=typename Struct::value_t;
        std::vector<data_t> dp;
        std::vector<value_t> res;
        void dfs0(int v,int pre,const graph_t& g);
        void dfs1(int v,int pre,data_t dPar,const graph_t& g);
        public:
        ReRooting(const graph_t& graph,Struct st=Struct(),int root=0);
        std::vector<value_t> get(){return res;};
    };

    template<class graph_t,class Struct>
    ReRooting<graph_t,Struct>::ReRooting(const graph_t& g,Struct st,int root)
        :N(g.size()),root(root),st(st),dp(N),res(N)
    {
        dfs0(root,-1,g);
        dfs1(root,-1,data_t(),g);
    }

    template<class graph_t,class Struct>
    void ReRooting<graph_t,Struct>::dfs0(int v,int pre,const graph_t& g){
        dp[v]=st.E();
        for(auto &e:g[v]){
            if(e.to==pre) continue;
            dfs0(e.to,v,g);
            dp[v]=st.merge(dp[v],st.mergeE(dp[e.to],e));
        }
        dp[v]=st.mergeV(dp[v],v);
    }
    
    template<class graph_t,class Struct>
    void ReRooting<graph_t,Struct>::dfs1(int v,int pre,data_t dPar,const graph_t& g){
        std::vector<data_t> tmp;
        tmp.reserve(g[v].size());
        for(auto &e:g[v]) if(e.to!=pre) tmp.push_back(st.mergeE(dp[e.to],e));
        int sz=tmp.size();
        std::vector<data_t> rsum(sz+1);
        rsum[sz]=st.E();
        for(int i=sz-1;i>=0;i--) rsum[i]=st.merge(rsum[i+1],tmp[i]);

        data_t lsum=st.E();
        int id=0;
        for(auto &e:g[v]){
            if(e.to==pre) continue;
            data_t cdsum=st.merge(st.merge(lsum,rsum[id+1]),dPar);
            data_t nextDPar=st.mergeE(st.mergeV(cdsum,v),e);
            dfs1(e.to,v,nextDPar,g);
            lsum=st.merge(lsum,tmp[id]);
            id++;
        }

        if(v!=root) tmp.push_back(dPar);
        res[v]=st.solve(v,tmp);
    }

}
#include<bits/stdc++.h>
using namespace std;
using namespace ProconLib;

struct Edge{
    int to;
};

template<typename edge_t>
struct Struct{
    using data_t=pair<int,int>;    
    using value_t=int;
    data_t E(){return make_pair(0,0);};
    data_t merge(data_t x,data_t y){return make_pair(x.first+y.first,max(x.second,y.second));};
    data_t mergeV(data_t x,int v){return x;};
    data_t mergeE(data_t x,const edge_t& e){return make_pair(x.first+2,x.second+1);}
    value_t solve(int v,const std::vector<data_t>& vec){
        int sum=0;
        int ma=0;
        for(int i=0;i<vec.size();i++) sum+=vec[i].first,ma=max(ma,vec[i].second);
        return sum-ma;
    };
};

using Graph=vector<vector<Edge>>;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin>>n;
    Graph g(n);
    for(int i=0;i+1<n;i++){
        int u,v; cin>>u>>v; u--,v--;
        g[u].push_back(Edge{v});
        g[v].push_back(Edge{u});
    }
    ReRooting<Graph,Struct<Edge>> rr(g);
    auto res=rr.get();
    for(int i=0;i<n;i++) cout<<res[i]<<"\n";
    return 0;
}
