{"raw_statement":[{"iden":"statement","content":"A year after his bacteria experiment, Jason decided to perform another experiment on a new bacteria specie which evolves in a special way. The initial form of the bacteria can be considered as an undirected tree with N nodes in terms of graph theory. Every hour, an edge (x, y) is built if there exists a node z such that, in the previous hour, there exists edge (x, z) and edge (y, z), but not edge (x, y). The bacteria keep evolving until no more edges can be formed.\n\nThe following graph shows a type of bacteria which requires 2 hours to fully evolve: \n\nAs it may take months if not years for the bacteria to evolve to its ultimate form, it is impossible for Jason to stay at the laboratory to observe the change of the bacteria throughout the entire process. Therefore, he wants you to calculate the time required for the bacteria to fully evolve, so that he can just get back to the laboratory on time. \n\nThe first line contains an integer N. (2 ≤ N ≤ 5 × 105)\n\nThe next N - 1 line each contains two integers u and v, which means there exists an edge between node u and v. (1 ≤ u, v ≤ N)\n\nThe given graph is guaranteed to be a valid tree.\n\nOutput an integer, the time (in hours) required for the bacteria to fully evolve.\n\n"},{"iden":"input","content":"The first line contains an integer N. (2 ≤ N ≤ 5 × 105)The next N - 1 line each contains two integers u and v, which means there exists an edge between node u and v. (1 ≤ u, v ≤ N)The given graph is guaranteed to be a valid tree."},{"iden":"output","content":"Output an integer, the time (in hours) required for the bacteria to fully evolve."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T = (V, E) $ be an undirected tree with $ |V| = N $ nodes and $ |E| = N - 1 $ edges.  \n\n**Evolution Rule**  \nAt each hour, for any triple of distinct nodes $ (x, y, z) $, if edges $ (x, z) $ and $ (y, z) $ exist and $ (x, y) $ does not, then add edge $ (x, y) $.  \nThis process repeats until no more edges can be added.  \n\n**Objective**  \nCompute the number of hours required until the graph becomes a **complete graph** (i.e., all pairs of nodes are connected), starting from tree $ T $, under the above rule.  \n\n**Constraints**  \n- $ 2 \\leq N \\leq 5 \\times 10^5 $  \n- The input graph is a tree.  \n\n**Output**  \nThe number of hours until no more edges can be added.","simple_statement":"Given a tree with N nodes, every hour new edges are added between any two nodes that have a common neighbor but are not yet connected. Keep adding edges until no more can be added. How many hours does it take until the graph becomes complete?","has_page_source":false}