AT_xmascon22_h Happy Game

$ 1 $ 個の入力ファイルにつき $ T $ 個のテストケースが与えられる．各テストケースで次のようなグラフ $ G $ が与えられるので，以下の問に答えよ． $ G $ は $ N $ 頂点 $ M $ 辺からなる連結な単純無向グラフである．頂点には $ 1 $ から $ N $ までの番号がついており， $ i $ 番目の辺は頂点 $ A_i $ と $ B_i $ を結んでいる ( $ 1 \le i \le M $ )． 今， $ G $ の頂点はすべて白色で塗られている．これから，くろうさとしろうさが次のゲームを行う． 1. まず，くろうさが好きな頂点を $ 1 $ 個選び，黒色で塗る． 2. その後，白色に塗られている頂点が存在する限り，しろうさが以下の操作を繰り返す： - 黒色で塗られている頂点に隣接しているような頂点を $ 1 $ 個または $ 2 $ 個選ぶ．選んだ頂点をすべて黒色で塗る． しろうさの操作回数を**スコア**と呼ぶ．くろうさの目的はスコアの最大化であり，しろうさの目的は最小化である．両者が最適に行動した場合のゲームのスコアを求めよ．

標準入力の $ 1 $ 行目にテストケースの個数 $ T $ が与えられる．その後， $ T $ 個のテストケースがそれぞれ以下の形式で与えられる． > $ N $ $ M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_M $ $ B_M $

各テストケースについて，答えを $ 1 $ 行で出力せよ．

### Sample Explanation 1 $ 1 $ 個目のテストケースでは，くろうさが頂点 $ 1 $ または $ 3 $ を選ぶことで，しろうさの操作回数が $ 2 $ 回になる． $ 2 $ 個目のテストケースでは，くろうさが選んだ頂点によらず，しろうさの操作回数が $ 2 $ 回になる． ### Constraints - $ 1 \le T \le 1.5 \times 10^5 $ ． - $ 2 \le N \le 3 \times 10^5 $ ． - $ N-1 \le M \le 3 \times 10^5 $ ． - $ 1 \le A_i,B_i \le N $ ( $ 1 \le i \le M $ )． - グラフ $ G $ は単純かつ連結である． - $ 1 $ 個の入力ファイルにおける $ N $ の総和は $ 3 \times 10^5 $ を超えない． - $ 1 $ 個の入力ファイルにおける $ M $ の総和は $ 3 \times 10^5 $ を超えない．