#include<bits/stdc++.h>
#define ll long long
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rev_rep(i,s,t) for(int i=(s);i>=(t);i--)
using namespace std;
int ci(){
	int x; scanf("%d",&x); return x;
}

enum{N=200023};

struct dt{ int sz; };
dt NIL = (dt){0};
dt operator+(const dt&a,const dt&b){
	return (dt){a.sz+b.sz};
}
class LCT{
private:
	struct node{
		node*fa,*c[2];
		dt x,x0;
		bool rev;
		#define lch c[0]
		#define rch c[1]
		void update(){
			x = lch->x + x0 + rch->x;
		}
		void downdate(){
			if( rev ){
				lch->rev^=1, rch->rev^=1;
				swap(lch,rch), rev=0;
			}
		}
	}d[N];
	bool chk(node*e){ return e->fa->rch==e; }
	bool nroot(node*e){
		return e->fa!=d&&(e->fa->lch==e||e->fa->rch==e);
	}
	node*get(node*x,bool o,node*y){
		return x->c[o]=y, y->fa=x;
	}
	void rotate(node*e){
		bool o = chk(e), ox= chk(e->fa);
		node*x = e->fa, *y = x->fa, *w = e->c[o^1];
		( nroot(x) ? y->c[ox]=e:0 ), e->c[o^1]=x, x->c[o]=w;
		( w!=d ? w->fa=x:0 ), x->fa=e, e->fa=y;
		x->update(), e->update();
	}
	void Downdate(node*e){
		if( nroot(e) ) Downdate(e->fa);
		e->downdate();
		d->x = d->x0 = NIL;
	}
	node*splay(node*e){
		Downdate(e);
		while( nroot(e) ){
			node*x = e->fa;
			if( nroot(x) ) rotate(chk(e)^chk(x)?e:x);
			rotate(e);
		} return e;
	}
	node*access(node*x){
		node*y=d;
		for(;x!=d;y=x,x=x->fa){
			splay(x), get(x,1,y), x->update();
		} return y;
	}
	node*makeroot(node*e){
		access(e), splay(e), e->rev^=1;
		return e;
	}
	node*findroot(node*e){
		access(e), splay(e);
		while( 1 ){
			e->downdate();
			if( e->lch==d ) break;
			e = e->lch;
		} return splay(e);
	}
	void link(node*x,node*y){
		makeroot(x)->fa = y;
	}
	void cut(node*x,node*y){
		makeroot(x), access(y), splay(y), y->lch=x->fa=d, x->update();
	}
	node*split(node*x,node*y){
		makeroot(x), access(y); return splay(y);
	}
public:
	void init(int n){
		*d = (node){d,d,d,NIL,NIL};
		rep(i,1,n) d[i] = (node){d,d,d,(dt){1},(dt){1}};
	}
	bool chk(int x,int y){
		return findroot(d+x)==findroot(d+y);
	}
	void add(int x,int y){
		link(d+x, d+y);
	}
	dt query(int x,int y){
		return split(d+x,d+y)->x;
	}
};

int a[N],b[N],d[N];

class UNI{
public:
	int fa[N];
	void init(int n){
		rep(i,1,n) fa[i] = i, a[i] = b[i] = i, d[i] = 0;
	}
	int fd(int x){
		return fa[x]==x ? x : fa[x]=fd(fa[x]);
	}
	int operator[](int x){ return fd(x); }
	bool merge(int x,int y){
		int fx=fd(x), fy=fd(y);
		if( fx!=fy ){
			fa[fx] = fy;
			return 1;
		} return 0;
	}
};

LCT lct;
UNI uni;

//#define DEBUG

#ifndef DEBUG
#define chk_max(x,y) (x<y ? (x=y,1):0)
#define chk_min(x,y) (x>y ? (x=y,1):0)
#endif // DEBUG

#ifdef DEBUG
#define _chk_max(x,y) (x<y ? (x=y,1):0)
#define _chk_min(x,y) (x>y ? (x=y,1):0)
#define chk_max(x,y) if( _chk_max(x,y) ) 
#define chk_min(x,y) if( _chk_min(x,y) ) 
#endif // DEBUG

multiset<int, greater<int> > st;

signed main(){
	int T = ci();
	while( T-- ){
		int n = ci(), m = ci();
		lct.init(n);
		uni.init(n);
		st.clear();
		rep(i,1,n) st.insert(d[i]);
		st.insert(-1e9);
		st.insert(-1e9);
		rep(i,1,m){
			int x = ci(), y = ci();
			int fx= uni[x], fy = uni[y];
			st.erase(st.lower_bound(d[fx]));
			st.erase(st.lower_bound(d[fy]));
			lct.add(x,y);
			vector<pair<int,int> > vec = {
				{a[fx], a[fy]},
				{a[fx], b[fy]},
				{b[fx], a[fy]},
				{b[fx], b[fy]},
			};
			int ans = d[fx];
			pair<int,int> pa = {a[fx], b[fx]};
			if( d[fx] < d[fy] ){
				ans = d[fy];
				pa = {a[fy], b[fy]};
			}
			for(auto p:vec){
		//printf("line %d: [%d %d] %d\n", __LINE__, p.first, p.second, lct.query(p.first, p.second).sz-1);
				if( chk_max(ans, lct.query(p.first, p.second).sz-1) ) pa = p;
			}
		//printf("line %d: d ab %d %d %d \n", __LINE__, d[fy], a[fy], b[fy]);
			uni.merge(fx,fy);
			d[fy] = ans;
			a[fy] = pa.first;
			b[fy] = pa.second;
		//printf("line %d: d ab %d %d %d \n", __LINE__, d[fy], a[fy], b[fy]);
			st.insert(ans);
		//printf("line %d:\n", __LINE__);
		//for(auto x:st) printf("%d ", x); puts("");
			int t1 = *st.begin();
			int t2 = *(++st.begin());
			int t3 = *(++(++st.begin()));
			printf("%d\n", max(max(t1,(t1+1)/2+(t2+1)/2+1), (t2+1)/2+(t3+1)/2+2));
		}
	}
	return 0;
}