AT_abc447_f [ABC447F] Centipede Graph

頂点に $ 1 $ から $ N $ の番号がついた $ N $ 頂点の木 $ T $ が与えられます。 $ i $ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を結んでいます。 正整数 $ k $ について「長さ $ k $ のムカデグラフ」を以下の手順で得られる頂点数 $ 3k $ のグラフと定義します。 - **頂点数** $ k $ のパスグラフを用意する。 - そのパスグラフの各頂点 $ v $ に対して、 $ v $ のみに隣接する $ 2 $ つの頂点を新たに追加する。 例えば、長さ $ 4 $ のムカデグラフは下図のようになります。  木 $ T $ の部分グラフとして含まれる「長さ $ x $ のムカデグラフ」のうち、最大の $ x $ を求めて下さい。 $ Q $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ Q $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_Q $ 各テストケースは以下の形式で与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $

$ Q $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースについて、答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて、頂点 $ 2,3,4,5,6,8 $ の $ 6 $ 頂点からなるグラフは「長さ $ 2 $ のムカデグラフ」となっています。 長さ $ 3 $ 以上のムカデグラフは部分グラフに含まれないため、答えは $ 2 $ です。よって $ 2 $ と出力してください。 ### Constraints - $ 1 \le Q $ - $ 3 \le N \le 2 \times 10^5 $ - $ 1 \le A_i, B_i \le N $ - 与えられるグラフは木 - 全てのテストケースにおける $ N $ の総和は $ 2 \times 10^5 $ 以下 - 入力される値は全て整数