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 <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define repd(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template
typedef pair<int, int> pii;
struct edge{int to, weight;};

#define MAX_V 100000
pii dfs(int prev, int v, const vector<edge> graph[MAX_V]){
    pii r(0, v);
    rep(i, graph[v].size()){
        struct edge e = graph[v][i];
        if(e.to == prev)continue;
        pii tmp = dfs(v, e.to, graph);
        tmp.first += e.weight;
        if( r.first < tmp.first) r =  tmp;
    }
    return r;
}

vector<edge> G[MAX_V];
void dijkstra(int s, vector<int> &d){
    priority_queue<pii, vector<pii>, greater<pii>> que;
    rep(i, d.size()) d[i] = inf;
    d[s] = 0;
    que.push(pii(0,s));
    while(que.size()){
        pii p = que.top();
//        cout << p.first <<  "," << p.second <<  endl;
        que.pop();
        int v = p.second;
        if(d[v] < p.first) continue;
//        cout << v <<  "," << p.first << "," << G[v].size() <<  endl;
        rep(i, G[v].size()){
            edge e = G[v][i];
//            cout << e.to <<  "," << v << "," <<  e.weight <<  endl;
            if(d[e.to] > d[v] + e.weight){
                d[e.to] = d[v] + e.weight;
                que.push(pii(d[e.to], e.to));
            }
        }
    }
}



int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    int n;
    cin>>n;
    
    rep(i,n-1){
        int u,v;
        
        cin>>u>>v;
        u--,v--;
        G[u].pb(edge{v,1});
        G[v].pb(edge{u,1});
    }
    
    
    pii r=dfs(-1,0,G);
    pii t = dfs(-1,r.second,G);
    int A = r.second;
    int B = t.second;
    
    vector<int> d1(n),d2(n);
    
    dijkstra(A,d1);
    dijkstra(B,d2);
    
//    cout<<A<<" "<<B<<endl;
    rep(i,n){
//        cout<<d1[i]<<" "<<d2[i]<<endl;
        int dist=max(d1[i],d2[i]);
        cout<<2*(n-1)-dist<<endl;
    }
    
    return 0;
}