1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35
36. 36
37. 37
38. 38
39. 39
40. 40
41. 41
42. 42
43. 43
44. 44
45. 45
46. 46
47. 47
48. 48
49. 49
50. 50
51. 51
52. 52
53. 53
54. 54
55. 55
56. 56
57. 57
58. 58
59. 59
60. 60
61. 61
62. 62
63. 63
64. 64
65. 65
66. 66
67. 67
68. 68
69. 69
70. 70
71. 71
72. 72
73. 73
74. 74
75. 75
76. 76
77. 77
78. 78

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using ii = pair<int, int>;
constexpr int MX = 1e5+5;

int ans, D[2*MX];
vector<int> G[MX], H[2*MX];

int main() {
	if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout);
	cin.tie(0)->sync_with_stdio(0);

	int T; cin >> T;
	while (T--) {
		int N, M; cin >> N >> M;
		for (int u = 1; u <= N; ++u) G[u].clear();
		for (int u = 1; u <= 2*N; ++u) H[u].clear();
		for (int i = 0; i < M; ++i) {
			int x, y; cin >> x >> y;
			G[x].push_back(y), G[y].push_back(x);
			H[x].push_back(y+N), H[y+N].push_back(x);
			H[y].push_back(x+N), H[x+N].push_back(y);
		}
		
		for (int u = 1; u <= 2*N; ++u) D[u] = 1e9;
		queue<int> q;
		D[1] = 0, q.push(1);
		while (q.size()) {
			int u = q.front(); q.pop();
			for (int v : H[u]) if (D[v] == 1e9)
				D[v] = D[u]+1, q.push(v);
		}

		if (*max_element(D+1, D+2*N+1) == 1e9) {
			cout << N-1 << '\n';
			continue;
		}

		/*vector<ii> C;
		C.emplace_back(0, 0);
		for (int u = 1; u <= N; ++u) {
			C.emplace_back(D[u], D[u+N]);
		}*/

		ans = 0;
		map<ii, int> f;
		map<ii, vector<int>> b;
		for (int u = 1; u <= N; ++u) {
			ii p(min(D[u], D[u+N]), max(D[u], D[u+N]));
			++f[p], b[p].push_back(u);
		}
		map<ii, int> ea;
		for (auto [p, c] : f) {
			int pr = ea[ii(p.f-1, p.s+1)];
			if (p.f+1 == p.s) {
				if (p.f == 0) ans += (c+1)/2;
				else if (f[ii(p.f-1, p.s-1)]) ans += max((c-pr)+(pr+1)/2, (c+1)/2);
				else {
					if (pr < c) ans += c-pr;
					ans += (c+1)/2;
				}
			}
			else {
				ans += c;
				if (p.f == 0) ea[p] = c;
				else if (f[ii(p.f-1, p.s-1)]) ea[p] += min(c, pr);
				else {
					if (pr < c) ans += c-pr;
					ea[p] = c;
				}
			}
		}
		cout << ans << '\n';
	}
}