Baby Sitting

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

using namespace std;

inline int nxt() { int x; cin >> x; return x; }

void solve() {
 int n = nxt(), m = nxt();
 vector<pair<int, int>> eds(m);
 for (auto& [x, y] : eds) {
  x = nxt()-1, y = nxt()-1;
 }
 
 auto can = [&](int k) {
  k-=1;
  vector<vector<int>> a(4*n), ar(4*n);
  //cerr << k+1 << "\n";
  auto add = [&](int x, int y) {
	  //cerr << x << " -> " << y << "\n";
	  a[x].push_back(y);
	  ar[y].push_back(x);
  };
  for (auto [x, y] : eds) {
   add(x+n, y);
   add(y+n, x);
  }
  for (int i = 0; i < n; ++i) {
   add(i+2*n, i+n);
   add(i+3*n, i+n);
   if(i%k) add(i+2*n, i+2*n-1);
   if(i%k != k-1 && i<n-1) add(i+3*n, i+3*n+1);
   if(i) add(i, i-1+2*n);
   if (i > k) add(i, i - k + 3*n);
   if(i<n-1) add(i, i+1+3*n);
   if (i+k<n) add(i, i + k + 2*n);
  }
  vector<int> order;
  vector<char> used(4*n);
  function<void(int)> dfs = [&](int v) {
	  if (used[v]) {
		  return;
	  }
	  used[v] = true;
	  for (int x : a[v]) {
		  dfs(x);
	  }
	  order.push_back(v);
  };
  for (int i = 0; i < 4*n; ++i) {
	  dfs(i);
  }
  reverse(all(order));
  vector<int> color(4*n, -1);
  int col = 0;
  function<void(int)> rdfs = [&](int v) {
	  color[v] = col;
	  for (int x : ar[v]) {
		  if (color[x] == -1) {
			  rdfs(x);
		  }
	  }
  };
  for (int v : order) {
	  if (color[v] != -1) {
		  continue;
	  }
	  rdfs(v);
	  col += 1;
  };
  for (int i = 0; i < n; ++i) {
	  if (color[i] == color[i + n]) {
		  return false;
	  }
  }
  return true;
 };
 
 int l = 1, r = n + 1;
 while (r > l + 1) {
  int k = (l+r)/2;
  (can(k)?l:r)=k;
 }
 cout << l << "\n";
}

int main()
{
    int t = nxt();
    while (t--) solve();
    return 0;
}