AT_abc428_e [ABC428E] Farthest Vertex

There is a tree with $ N $ vertices numbered $ 1 $ to $ N $ . The $ i $ -th edge connects vertices $ A_i $ and $ B_i $ . Define the distance between vertices $ u $ and $ v $ as the number of edges in the path with endpoints at vertices $ u $ and $ v $ . (This path is uniquely determined.) Solve the following problem for $ v = 1, 2, \dots, N $ . - Among vertices $ 1, 2, \dots, N $ , output the number of the vertex that has the maximum distance from vertex $ v $ . If there are multiple vertices that satisfy the condition, output **the vertex with the largest number**.

The input is given from Standard Input in the following format: > $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $

Output $ N $ lines. The $ i $ -th line should contain the answer for $ v=i $ .

### Sample Explanation 1 The vertex with the maximum distance from vertex $ 1 $ is vertex $ 3 $ . The vertices with the maximum distance from vertex $ 2 $ are vertices $ 1 $ and $ 3 $ . Among them, vertex $ 3 $ , which has the larger number, is the answer. The vertex with the maximum distance from vertex $ 3 $ is vertex $ 1 $ . ### Constraints - $ 2 \leq N \leq 5 \times 10^5 $ - $ 1 \leq A_i \lt B_i \leq N $ - The graph given in the input is a tree. - All input values are integers.