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>

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))

using namespace std;

using i32 = int;
using i64 = long long;
using u64 = unsigned long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vu64 = vector<u64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
inline u64 xorshift() { static u64 x = 88172645463325252ull; x = x ^ (x << 7); return x = x ^ (x >> 9); }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T power(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
template <typename T, typename S> istream& operator>>(istream &is, pair<T, S> &p) { is >> p.first >> p.second; return is; }
template <typename T, typename S> ostream& operator<<(ostream &os, pair<T, S> &p) { os << p.first << ' ' << p.second; return os; }

struct UnWeightedGraph {
  vector<vector<int>> edges;
  int n;
  UnWeightedGraph(int n) : n(n) {
    edges = vector<vector<int>>(n);
  }
  void add_edge(int from, int to) {
    edges[from].push_back(to);
  }
  vector<int>& operator[](int x) {
    return edges[x];
  }
};

void solve() {
  int N; cin >> N;
  auto graph = UnWeightedGraph(N);
  rep(i, N - 1) {
    int v, u; cin >> v >> u;
    v--, u--;
    graph.add_edge(v, u);
    graph.add_edge(u, v);
  }

  vector<vi32> dp(N);
  vector<int> par(N, -1);
  vector<int> ans(N);

  function<int(int, int)> dfs = [&](int v, int p) {
    int n = graph[v].size();
    dp[v] = vi32(n);

    int ret = 0;
    rep(i, n) {
      int u = graph[v][i];
      if (u == p) {
        par[v] = i;
        continue;
      }
      dp[v][i] = dfs(u, v) + 1;
      amax(ret, dp[v][i]);
    }
    return ret;
  };

  function<void(int, int, int)> bfs = [&](int v, int res_p, int p) {
    if (p != -1) {
      dp[v][par[v]] = res_p;
    }
    int n = graph[v].size();

    vi32 dpl(n + 1), dpr(n + 1);
    rep(i, n) dpl[i + 1] = max(dpl[i], dp[v][i]);
    rrep(i, n) dpr[i] = max(dpr[i + 1], dp[v][i]);

    ans[v] = dpr[0];

    rep(i, n) {
      if (i == par[v]) continue;
      int u = graph[v][i];
      bfs(u, max(dpl[i], dpr[i + 1]) + 1, v);
    }
  };

  dfs(0, -1);
  bfs(0, 0, -1);

  rep(i, N) {
    cout << (N - 1) * 2 - ans[i] << '\n';
  }
}

