{"raw_statement":[{"iden":"statement","content":"You are given $n + 1$ nodes and $n -1$ edges where the first $n$ nodes are a tree and node $n + 1$ is in its own component. For each node $i$ from $1... n$, answer the following question:\n\nIf an edge was added from node $i$ to node $n + 1$, what would the diameter of the created tree be? (Notice that the $n + 1$ nodes will be a tree if this edge was added).\n\nThe first line will contain a single integer $n$, the number of nodes in the tree initial tree. $n -1$ lines follow, each containing two different integers, describing the edges initially in the tree. Additional constraint on input: these edges will form a tree on the first $n$ nodes.\n\n$1 <= n <= 3 * 10^5$\n\nPrint $n$ integers, each on their own line. The $i$th is the diameter of the new tree if you were to add an edge from node $i$ to node $n + 1$.\n\n"},{"iden":"input","content":"The first line will contain a single integer $n$, the number of nodes in the tree initial tree. $n -1$ lines follow, each containing two different integers, describing the edges initially in the tree. Additional constraint on input: these edges will form a tree on the first $n$ nodes.$1 <= n <= 3 * 10^5$"},{"iden":"output","content":"Print $n$ integers, each on their own line. The $i$th is the diameter of the new tree if you were to add an edge from node $i$ to node $n + 1$."},{"iden":"examples","content":"Input1\nOutput1\nInput3\n3 2\n2 1\nOutput3\n2\n3\nInput5\n4 2\n1 4\n5 4\n3 4\nOutput3\n3\n3\n2\n3\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T = (V, E) $ be a tree with $ V = \\{1, 2, \\dots, n\\} $ and $ |E| = n - 1 $. Let $ v_{n+1} $ be an isolated node.  \n\nFor each $ i \\in \\{1, \\dots, n\\} $, define $ T_i = (V \\cup \\{v_{n+1}\\}, E \\cup \\{\\{i, v_{n+1}\\}\\}) $, the tree formed by adding edge $ (i, v_{n+1}) $.\n\n**Constraints**  \n$ 1 \\le n \\le 3 \\cdot 10^5 $\n\n**Objective**  \nFor each $ i \\in \\{1, \\dots, n\\} $, compute the diameter of $ T_i $, defined as:  \n$$\n\\text{diam}(T_i) = \\max_{u,v \\in V \\cup \\{v_{n+1}\\}} \\text{dist}_{T_i}(u, v)\n$$","simple_statement":"You are given a tree with n nodes and one extra node (node n+1) not connected to anything. For each node i from 1 to n, imagine connecting it to node n+1. After this connection, you get a new tree with n+1 nodes. Find the diameter of that new tree for each i.","has_page_source":false}