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 int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cerr<<(#v)<<":";for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;
#define printVS(vs) cerr<<(#vs)<<":"<<endl;for(auto(s):(vs)){cerr<<(s)<< endl;}
#define printVV(vv) cerr<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;}
#define printP(p) cerr<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cerr<<(#vp)<<":"<<endl;for(auto(p):(vp)){cerr<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cerr << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cerr << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 1ll << 60;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;

int dp[100000];
int mi[100000];

int dfs(int now, int pre, const Graph& G) {
    for (auto nxt : G[now]) {
        if (nxt == pre) continue;
        chmax(dp[now], dfs(nxt, now, G) + 1);
    }
    return dp[now];
}

void dfs2(int now, int pre, int prop, const Graph& G) {
    vector<Pii> vp;
    vp.emplace_back(0, -1);
    for (auto nxt : G[now]) {
        if (nxt == pre) vp.emplace_back(prop + 1, nxt);
        else vp.emplace_back(dp[nxt] + 1, nxt);
    }
    sort(rall(vp));
    mi[now] = vp[0].first;
    for (auto nxt : G[now]) {
        if (nxt == pre) continue;
        dfs2(nxt, now, vp[vp[0].second == nxt].first, G);
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n;
    cin >> n;
    Graph G(n);
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }

    dfs(0, -1, G);
    dfs2(0, -1, 0, G);

    rep(i, n) cout << 2 * (n - 1) - mi[i] << endl;
}