AT_abc447_f [ABC447F] Centipede Graph

You are given a tree $ T $ with $ N $ vertices numbered $ 1 $ to $ N $ . The $ i $ -th edge connects vertices $ A_i $ and $ B_i $ . For a positive integer $ k $ , define a "centipede graph of length $ k $ " as a graph with $ 3k $ vertices obtained by the following procedure: - Prepare a path graph with $ k $ **vertices**. - For each vertex $ v $ of the path graph, add two new vertices adjacent only to $ v $ . For example, a centipede graph of length $ 4 $ is as shown in the figure below.  Find the maximum $ x $ such that a "centipede graph of length $ x $ " is contained as a subgraph of tree $ T $ . $ Q $ test cases are given; solve each of them.

The input is given from Standard Input in the following format: > $ Q $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_Q $ Each test case is given in the following format: > $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $

Output $ Q $ lines. The $ i $ -th line should contain the answer for the $ i $ -th test case.

### Sample Explanation 1 For the first test case, the graph consisting of the six vertices $ 2,3,4,5,6,8 $ forms a "centipede graph of length $ 2 $ ". No centipede graph of length $ 3 $ or more is contained as a subgraph, so the answer is $ 2 $ . Thus, output $ 2 $ . ### Constraints - $ 1 \le Q $ - $ 3 \le N \le 2 \times 10^5 $ - $ 1 \le A_i, B_i \le N $ - The given graph is a tree. - The sum of $ N $ over all test cases is at most $ 2 \times 10^5 $ . - All input values are integers.