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
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1595

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
#include<complex>
#include <cassert>

using namespace std;

#define ll long long
#define ld long double
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

const double PI=acos(-1);
const double EPS=1e-9; //うまくいかなかったらゆるめる

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef vector<pii> vp;
typedef vector<vi> vvi;

int gcd(int a, int b){if(b==0) return a;return gcd(b,a%b);}
int lcm(int a, int b){return a/gcd(a,b)*b;}


struct edge{
  int to, cost;
};
vector<vector<edge>  >g;
vector<int> d;

void dfs(int now, int par){
    for(auto e: g[now])if(e.to != par){
        dfs(e.to,now);
        d[now] = max(d[now], d[e.to] + e.cost);
    }
}

void dfs2(int now, int d_par, int par){
    vp d_child;//深さ、頂点番号
    d_child.push_back(pii(0,-1));
    for(auto e: g[now]){
        if(e.to == par){
            d_child.push_back(pii(d_par + e.cost, e.to));
        }else{
            d_child.push_back(pii(d[e.to] + e.cost, e.to));
        }
    }
    sort(all(d_child));
    reverse(all(d_child));
    d[now] = max(d[now], d_child[0].first);
    for(auto e: g[now])if(e.to != par){
        dfs2(e.to, d_child[d_child[0].second == e.to].first,now);
    }
}

signed main(void) {
    int n;
    cin >> n;
    g.resize(n);
    d = vi(n,0);
    rep(i,n-1){
        int a,b,c;
        cin >> a >> b;
        a--,b--;
        edge e1 = {b,1};
        g[a].push_back(e1);
        edge e2 = {a,1};
        g[b].push_back(e2);
    }
    dfs(0,-1);
    //rep(i,n)cout << d[i] << endl;
    dfs2(0,0,-1);
    //rep(i,n)cout << d[i] << endl;
    rep(i,n){
        cout << (n-1)*2 - d[i] << endl;
    }
}

