#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <vector>#include <queue>using namespace std;int n,m;int r1[10010],r2[10010];struct Edge{    int from,to,cap,flow;};const int maxn = 20000;struct Dinic{    int s,t,m;    vector<Edge> edges;    vector<int> G[maxn];    bool vis[maxn];    int d[maxn];    int cur[maxn];    void init(int n)    {        for (int i=0;i<=n;i++){            G[i].clear();        }        edges.clear();    }    void addedge(int from,int to,int cap)    {        edges.push_back((Edge){from,to,cap,0});        edges.push_back((Edge){to,from,0,0});        m=edges.size();        G[from].push_back(m-2);        G[to].push_back(m-1);    }    bool bfs(){        memset(vis,0,sizeof vis);        queue<int>Q;        Q.push(s);        d[s]=0;        vis[s]=1;        while (!Q.empty())        {            int u=Q.front();Q.pop();            for (int i=0;i<G[u].size();i++){                Edge& e=edges[G[u][i]];                if (!vis[e.to] && e.cap>e.flow){                    vis[e.to]=1;                    d[e.to]=d[u]+1;                    Q.push(e.to);                }            }        }        return vis[t];    }    int DFS(int x,int a)    {        if (x==t || a==0 ) return a;        int flow=0,f;        for (int& i=cur[x];i<G[x].size();i++){            Edge& e =edges[G[x][i]];            if (d[x]+1==d[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow))>0)){                e.flow+=f;                edges[G[x][i]^1].flow-=f;                flow+=f;                a-=f;                if (a==0) break;            }        }        return flow;    }    int maxflow(int s,int t){        this->s=s;this->t=t;        int flow=0;        while (bfs()){            memset(cur,0,sizeof cur);            flow+=DFS(s,10000000);        }        return flow;    }}dinic;int main(){    int t;    scanf("%d",&t);    while (t--)    {        scanf("%d",&n);        scanf("%d",&m);        for (int i=1;i<=m;i++) scanf("%d%d",&r1[i],&r2[i]);        int l=0,r=m+1,mid;        int ans=0;        while (l<r)        {            mid=(l+r)>>1;            dinic.init(n+m+2);            for (int i=1;i<=m;i++){              dinic.addedge(0,i,1);              dinic.addedge(i,r1[i]+m,1);              dinic.addedge(i,r2[i]+m,1);            }            for (int i=1;i<=n;i++) dinic.addedge(i+m,n+m+1,mid);            int res=dinic.maxflow(0,n+1+m);            if (res==m){                r=mid;                ans=mid;            }            else l=mid+1;        }        printf("%d\n",ans);    }    return 0;}