把列看成左部点，行看成右部点，最终要求主对角线为1，可以认为是一个行至少对应了一个列，因为可以通过交换把这种情况换成主对角线。

只需要最大匹配是否等于n即可。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int MAXN = 100005;const int INF = 1<<30;int n,m,S,T;inline int rd(){    int ret=0,f=1;char c;    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;    while(isdigit(c))ret=ret*10+c-'0',c=getchar();    return ret*f;}struct Edge{    int next,to,w;}e[MAXN];int ecnt=1,head[MAXN];inline void add(int x,int y,int w){    e[++ecnt].next = head[x];    e[ecnt].to = y;    e[ecnt].w = w;    head[x] = ecnt;}queue
         
           Q;int dis[MAXN];bool bfs(){    memset(dis,0,sizeof(dis));    Q.push(S);dis[S]=1;    while(!Q.empty()){        int top=Q.front();Q.pop();        for(int i=head[top];i;i=e[i].next){            int v=e[i].to;            if(dis[v]||!e[i].w) continue;            Q.push(v);dis[v]=dis[top]+1;        }    }    return dis[T];}int cur[MAXN];int dfs(int x,int flow){    if(x==T) return flow;    int used=0,tmp;    for(int i=cur[x];i;i=e[i].next){        int v=e[i].to;        if(dis[v]!=dis[x]+1) continue;        tmp=dfs(v,min(flow-used,e[i].w));        e[i].w-=tmp;e[i^1].w+=tmp;used+=tmp;        if(e[i].w) cur[x]=i;        if(flow==used) return flow;    }    if(!used) dis[x]=0;    return used;}int mxflow;void dinic(){    mxflow=0;    while(bfs()){        memcpy(cur,head,sizeof(head));        mxflow+=dfs(S,INF);    }}void solve(){    ecnt=1;memset(head,0,sizeof(head));    n=rd();    int x;    for(int i=1;i<=n;i++){        for(int j=1;j<=n;j++){            if(rd()) add(i,n+j,1),add(n+j,i,0);        }    }    S=3*n,T=3*n+1;    for(int i=1;i<=n;i++) add(S,i,1),add(i,S,0);    for(int i=1;i<=n;i++) add(n+i,T,1),add(T,n+i,0);    dinic();    if(mxflow==n) puts("Yes");    else puts("No");}int main(){    int t;    t=rd();    while(t--) solve();    return 0;}