#include
     
      #include
      
       #include
       
        #define MAXN 1010using namespace std;int map[MAXN][MAXN],n,dis[MAXN];int min(int x,int y){
    return x
        

q; memset(dis,-1,sizeof(dis)); dis[1]=0; q.push(1); while(!q.empty()) { int t=q.front(); q.pop(); for(i=1;i<=n;i++) { if(map[t][i]&&dis[i]<0) { dis[i]=dis[t]+1; q.push(i); } } } if(dis[n]>0) return 1; return 0;}int dfs(int u,int low){ int i,j,a; if(u==n) return low; for(i=1;i<=n;i++) { if(map[u][i]&&dis[i]==dis[u]+1) { a=dfs(i,min(map[u][i],low)); if(a<=0)continue; map[u][i]-=a; map[i][u]+=a; return a; } } return 0;}int main(){ int t,ff=0,i,j,m; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); memset(map,0,sizeof(map)); for(i=0;i