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 <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>
#include <sys/time.h>
#include <random>


#define fs first
#define sc second
#define endl "\n"

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef pair<ll, ll> P;


class Graph{
    struct edge{
        int vertice;
        ll weight;
    };

    vector<vector<edge>> g;
    unsigned int n;

public:
    Graph(unsigned int n): n{n}{
        g.resize(n);
    }

    void add_edge(int u, int v){
        g[u].emplace_back(edge{v, 1});
    };

    void add_edge(int u, int v, ll w){
        g[u].emplace_back(edge{v, w});
    }

    vector<edge>& get_edge(int v){
        return g[v];
    }

    unsigned int size(){
        return n;
    }

    vector<edge>& operator[](int v){
        return get_edge(v);
    }
};


/**
 * parentFun(merge(childFun(dp_c1), childFun(dp_c2), \ldots, childFun(dp_cm))
 * @tparam T
 */
template <typename T>
class ReRooting{
private:
    using Operate = function<T(T, T)>;  // monoid
    using OperateNode = function<T(T, int)>;

    Graph g;
    Operate merge;
    T u;                 // Operateについての単位元
    OperateNode childFun, parentFun;

    vector<vector<T>> dp;
    vector<T> res;

    T dfs1(int v, int prev){
        T res = u;
        for(int i = 0; i < g[v].size(); i++){
            auto e = g[v][i];
            if(e.vertice == prev)   continue;
            dp[v][i] = dfs1(e.vertice, v);
            res = merge(res, childFun(dp[v][i], e.vertice));
        }

        return parentFun(res, v);
    }

    void dfs2(int v, int prev, T fromP){
        int n = g[v].size();        // vからの辺を持つ頂点数
        for(int i = 0; i < n; i++){
            auto e = g[v][i];
            if(e.vertice == prev){
                dp[v][i] = fromP;
                break;
            }
        }

        vector<T> cumFromLeft(n + 1), cumFromRight(n + 1);
        cumFromLeft[0] = u; cumFromRight[n] = u;
        for(int i = 0; i < n; i++){
            cumFromLeft[i+1] = merge(cumFromLeft[i], childFun(dp[v][i], v));
        }
        for(int i = n-1; i >= 0; i--){
            cumFromRight[i] = merge(cumFromRight[i+1], childFun(dp[v][i], v));
        }

        for(int i = 0; i < n; i++){
            auto e = g[v][i];
            if(e.vertice == prev)   continue;
            T fromC = parentFun(merge(cumFromLeft[i], cumFromRight[i+1]), v);
            dfs2(e.vertice, v, fromC);
        }

        res[v] = parentFun(cumFromLeft[n], v);
    }


public:
    ReRooting(Graph& g_, Operate merge_, T u_, OperateNode childFun_, OperateNode parentFun_):
            g(g_), merge(merge_), u(u_), childFun(childFun_), parentFun(parentFun_){
        dp.resize(g.size());
        for(int i = 0; i < g.size(); i++){
            dp[i].resize(g[i].size());
        }
        res.resize(g.size());
    }

    void calc(int root = 0){
        dfs1(root, root);
        dfs2(root, root, u);
    }

    T get(int v){
        return res[v];
    }
};


int main(){
    int n;
    cin >> n;
    Graph g(n);
    for(int i = 0; i < n-1; i++){
        int x, y;   cin >> x >> y;
        x--; y--;
        g.add_edge(x, y);
        g.add_edge(y, x);
    }

    ReRooting<P> reroot(g,
                        [](P x, P y){ P tmp = P(x.fs + y.fs, max(x.sc, y.sc)); return tmp; },
                        P(0LL, 0LL),
                        [](P x, int v){ P tmp(x.fs + 2, x.sc + 1); return tmp; },
                        [](P x, int v) { return x; });

    reroot.calc(0);
    for(int i = 0; i < n; i++){
        cout << reroot.get(i).fs - reroot.get(i).sc << endl;
    }





    return 0;
}

