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 <cstdio>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <functional>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <vector>
#include <array>
#include <tuple>
#include <utility>
#include <numeric>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <assert.h>
#include <cstdlib>
#include <list>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;

template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {
    return s << "(" << p.first << ", " << p.second << ")";
}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
    s << "[";
    for (int i = 0; i < v.size(); i++) s << (i == 0 ? "" : ", ") << v[i];
    s << "]";
    return s;
}

#define ALL(a) (a).begin(), (a).end()

using Weight = int;

// ??????????????????
struct Edge {
    int from, to;
    Weight weight;

    Edge() {}
    Edge(int to) : from(-1), to(to), weight(-1) {}
    Edge(int from, int to) : from(from), to(to), weight(-1) {}
    Edge(int from, int to, Weight weight) : from(from), to(to), weight(weight) {}

    bool operator<(const Edge& e) const {
        return (weight != e.weight) ? (weight < e.weight) : (from < e.from);
    }
    bool operator>(const Edge& e) const {
        return (weight != e.weight) ? (weight > e.weight) : (from > e.from);
    }
};

using Arc = Edge;
using Graph = vector<vector<Edge>>;
using DGraph = vector<vector<Arc>>;

using Tree = Graph;

// ?????????????????????????????¨????????????????????????!
using GArray = vector<Weight>;
using GMatrix = vector<GArray>;

// ??????4????????¢??°???????????°??????????????????????????§?????§?????????
void add_edge(Graph& g, int u, int v, Weight w = -1) {
    g[u].push_back(Edge(u, v, w));
    g[v].push_back(Edge(v, u, w));
}

void add_arc(DGraph& dg, int u, int v, Weight w = -1) {
    dg[u].push_back(Arc(u, v, w));
}

const int GM_INF = (1LL << 25);

void init_gmatrix(GMatrix& gm) {
    for (int u = 0; u < gm.size(); u++) {
        for (int v = 0; v < gm[u].size(); v++) {
            gm[u][v] = GM_INF;
        }
    }
}

void add_edge(GMatrix& gm, int u, int v, Weight w = -1) {
    gm[u][v] = w;
    gm[v][u] = w;
}

void add_arc(GMatrix& gm, int u, int v, Weight w = -1) {
    gm[u][v] = w;
}

const int MAX_N = 100010;

Graph tree;

int cost1[MAX_N],   // ????????????????????¨????????¨?????¨???????????¬??°
    cost2[MAX_N];

int dfs1(int id, int par) {
    int ret = 0;
    for (Edge& e : tree[id]) {
        if (e.to == par) continue;
        ret = max(ret, dfs1(e.to, id) + 1);
    }
    // cout << "[id] " << id << " [ret] " << ret << endl;
    return cost1[id] = ret;
}

void dfs2(int id, int d_par, int par) {
    vector<PII> info;
    info.push_back(make_pair(0, -1));

    for (Edge& e : tree[id]) {
        if (e.to == par) {
            info.push_back(make_pair(d_par + 1, e.to));
        } else {
            info.push_back(make_pair(cost1[e.to] + 1, e.to));
        }
    }
    sort(ALL(info), greater<PII>());

    int ret = info[0].first;
    for (Edge& e : tree[id]) {
        if (e.to == par) continue;
        if (e.to == info[0].second) {
            dfs2(e.to, info[1].first, id);
        } else {
            dfs2(e.to, info[0].first, id);
        }
    }
    // cout << "[id] " << id + 1 << " [ret] " << ret << endl;
    cost2[id] = ret;
}

int main() {
    int n;
    cin >> n;

    tree.resize(n);

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        add_edge(tree, u, v);
    }

    dfs1(0, -1);
    dfs2(0, 0, -1);
    for (int i = 0; i < n; i++) {
        cout << (n - 1) * 2 - cost2[i] << endl;
    }

    /*
    int a;
    while (cin >> a, a >= 0) {
        cout << "[cost1] " << cost1[a] << " [cost2] " << cost2[a] << endl;
    }
    */

    return 0;
}