問題文

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 \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 を超えない．

入力例 1

2
3 2
1 2
2 3
4 4
1 2
2 3
3 4
4 1

出力例 1

2
2

1 個目のテストケースでは，くろうさが頂点 1 または 3 を選ぶことで，しろうさの操作回数が 2 回になる．

2 個目のテストケースでは，くろうさが選んだ頂点によらず，しろうさの操作回数が 2 回になる．

入力例 2

2
5 8
5 1
2 3
2 4
5 2
1 3
3 5
1 4
4 5
20 40
13 10
13 19
12 15
14 7
1 17
8 17
13 7
10 7
16 2
5 20
12 1
3 12
19 7
8 20
20 16
2 5
14 13
3 9
13 6
5 16
4 1
2 4
8 16
14 10
8 2
11 8
15 3
18 5
17 20
11 17
6 10
16 11
15 1
9 6
19 6
8 4
2 11
20 11
10 19
16 18

出力例 2

2
11