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 <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


struct Edge{
	Edge(int arg_to,int arg_cost){
		to = arg_to;
		cost = arg_cost;
	}
	int to,cost;
};


struct Info{
	Info(int arg_node_id,int arg_depth){
		node_id = arg_node_id;
		depth = arg_depth;
	}
	bool operator<(const struct Info &arg) const{
		return depth < arg.depth;
	}

	int node_id,depth;
};

struct RevInfo{
	RevInfo(int arg_node_id,int arg_depth){
		node_id = arg_node_id;
		depth = arg_depth;
	}
	bool operator<(const struct RevInfo &arg) const{
		return depth > arg.depth;
	}

	int node_id,depth;
};

struct Data{
	void set(int arg_max_dist1,int arg_max_dist2,int arg_node1,int arg_node2){
		max_dist1 = arg_max_dist1;
		max_dist2 = arg_max_dist2;
		node1 = arg_node1;
		node2 = arg_node2;
	}
	int max_dist1,max_dist2,node1,node2,parent_dir_max_dist;
};

int *depth_table,*parent;
vector<Edge> G[100000];
Data data[100000];

void calcDepth(int node_id,int depth,int parent_id){
	depth_table[node_id] = depth;
	parent[node_id] = parent_id;
	for(int i = 0; i < G[node_id].size(); i++){
		if(G[node_id][i].to == parent_id)continue;
		calcDepth(G[node_id][i].to,depth+1,node_id);
	}
}

int main(){

	int N;
	scanf("%d",&N);

	depth_table = new int[N];
	parent = new int[N];

	for(int i = 0; i < N; i++){
		data[i].max_dist1 = -1;
		data[i].max_dist2 = -1;
		data[i].parent_dir_max_dist = -1;
	}

	int from,to;
	for(int loop = 0; loop < N-1; loop++){
		scanf("%d %d",&from,&to);
		from--;
		to--;
		G[from].push_back(Edge(to,1));
		G[to].push_back(Edge(from,1));
	}

	calcDepth(0,0,-1);

	priority_queue<Info> Q;

	for(int i = 0; i < N; i++){
		Q.push(Info(i,depth_table[i]));
	}


	int max1,max2,node1,node2;
	while(!Q.empty()){

		max1 = 0,max2 = 0;

		for(int i = 0; i < G[Q.top().node_id].size(); i++){
			if(G[Q.top().node_id][i].to == parent[Q.top().node_id])continue;

			if(max1 < data[G[Q.top().node_id][i].to].max_dist1 + G[Q.top().node_id][i].cost){
				max2 = max1;
				node2 = node1;
				max1 = data[G[Q.top().node_id][i].to].max_dist1 + G[Q.top().node_id][i].cost;
				node1 = G[Q.top().node_id][i].to;
			}else if(max2 < data[G[Q.top().node_id][i].to].max_dist1 + G[Q.top().node_id][i].cost){
				max2 = data[G[Q.top().node_id][i].to].max_dist1 + G[Q.top().node_id][i].cost;
				node2 = G[Q.top().node_id][i].to;
			}
		}
		data[Q.top().node_id].set(max1,max2,node1,node2);
		Q.pop();
	}

	priority_queue<RevInfo> RevQ;

	for(int i = 0; i < N; i++){
		RevQ.push(RevInfo(i,depth_table[i]));
	}

	int parent_node;
	while(!RevQ.empty()){

		if(parent[RevQ.top().node_id] == -1){
			RevQ.pop();
			continue;
		}

		parent_node = parent[RevQ.top().node_id];

		if(data[parent_node].parent_dir_max_dist != -1){
			data[RevQ.top().node_id].parent_dir_max_dist = max(data[RevQ.top().node_id].parent_dir_max_dist,data[parent_node].parent_dir_max_dist+1);
		}

		if(data[parent_node].node1 != RevQ.top().node_id){
			data[RevQ.top().node_id].parent_dir_max_dist = max(data[RevQ.top().node_id].parent_dir_max_dist,data[parent_node].max_dist1+1);
		}else if(data[parent_node].max_dist2 != -1 && data[parent_node].node2 != RevQ.top().node_id){
			data[RevQ.top().node_id].parent_dir_max_dist = max(data[RevQ.top().node_id].parent_dir_max_dist,data[parent_node].max_dist2+1);
		}
		RevQ.pop();
	}

	for(int i = 0; i < N; i++){
		printf("%d\n",2*(N-1)-max(data[i].parent_dir_max_dist,data[i].max_dist1));
	}

	return 0;
}