//闲敲棋子落灯花//
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int NN = 6e5 + 500;
stack<int> s;
int dfn[NN], low[NN], timer, cnt, col[NN];
bool vis[NN];
vector<int> G[NN];
vector<int> Neo[NN];
void tarjan(int u) {
vis[u] = true;
low[u] = dfn[u] = ++timer;
s.push(u);
for (auto v : Neo[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (vis[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
cnt++;
while (1) {
int x = s.top(); s.pop();
vis[x] = false;
col[x] = cnt;
if (x == u) break;
}
}
}
int N, M;
void add_edge(int x, int y) {
Neo[x].push_back(y);
return;
}
void build(int p, int l, int r) {
if (l == r) {
add_edge(p + 2 * N, l + N);
return;
}
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
add_edge(p + 2 * N, (p << 1) + 2 * N);
add_edge(p + 2 * N, (p << 1 | 1) + 2 * N);
return;
}
void add(int p, int l, int r, int ql, int qr, int x) {
if (ql <= l && r <= qr) {
add_edge(x, p + 2 * N);
return;
}
int mid = (l + r) >> 1;
if (ql <= mid) add(p << 1, l, mid, ql, qr, x);
if (qr >= mid + 1) add(p << 1 | 1, mid + 1, r, ql, qr, x);
return;
}
bool check(int k) {
if (k == 1) return true;
for (int i = 0; i <= 2 * N; i++)
Neo[i].clear();
for (int i = 1; i <= N; i++)
for (auto& v : G[i])
add_edge(i + N, v);
for (int i = 1; i <= N; i++) {
int L = max(1, i - k + 1), R = i - 1;
if (L <= R) add(1, 1, N, L, R, i);
L = i + 1; R = min(N, i + k - 1);
if (L <= R) add(1, 1, N, L, R, i);
}
while (s.size()) s.pop();
timer = 0, cnt = 0;
for (int i = 1; i <= 6 * N; i++)
low[i] = dfn[i] = vis[i] = 0;
for (int i = 1; i <= 6 * N; i++)
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= N; i++)
if (col[i] == col[i + N])
return false;
return true;
}
void solve() {
cin >> N >> M;
for (int i = 0; i <= 6 * N; i++) {
G[i].clear();
Neo[i].clear();
}
for (int i = 0; i < M; i++) {
int u, v; cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
build(1, 1, N);
int l = 1, r = N;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << l << '\n';
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) {
solve();
}
}