玄学匈牙利

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define ul unsigned long long
#define RG register int
#define rg register int
#define ll long long
#define il inline
#define INF 2147483647
#define SZ 1000000
using namespace std;
il int GI()
{
  RG x=0,o=1;char ch=getchar();
  while((ch!='-') && (ch<'0'||ch>'9')) ch=getchar();
  if(ch == '-') o=0,ch=getchar();
  while(('0'<=ch) && (ch<='9')) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
  return o?x:-x;
}
struct Edge{int to,nxt;}e[SZ];
int Ehead[SZ],Ecnt=1;
il void Eadd(int u,int v)
{
  e[Ecnt]=(Edge){v,Ehead[u]};
  Ehead[u]=Ecnt++;
}
int n,I[1000],J[1000];

int pre[SZ],mat[SZ],vis[SZ];
queue <int> Q; bool flg;
il int Hung()
{
  RG Ans = 0;
  memset(vis,-1,sizeof(vis));
  memset(mat,-1,sizeof(mat));
  for(RG i=1;i<=n;++i)
  {
    if(mat[i]!=-1) continue;
    while(!Q.empty()) Q.pop();
    Q.push(i) , pre[i]=-1, flg=0;
    while((!Q.empty()) && (!flg))
    {
      RG u=Q.front();Q.pop();
      for(RG j=Ehead[i];j;j=e[j].nxt)
      {
        RG v=e[i].to;
        if(vis[v]==i) continue;
        vis[v]=1;
        if(mat[v]>0) pre[mat[v]]=u,Q.push(v);
        else
        {
          flg = 1;
          RG a=u,b=v;
          while(a!=-1)
          {
            RG c=mat[a];
            mat[a]=b,mat[b]=a;
            a=pre[a],b=c;
          }
        }
      }
    }
    if(mat[i]!=-1) ++Ans;
  }
  return Ans;
}

queue <int> Q;bool flg;
il int Hung()
{
  rg Ans=0;
  memset(vis,-1,sizeof(vis));
  memset(mat,-1,sizeof(mat));
  for(rg i=1;i<=n;++i)
  {
    if( I[i] && J[i] ) continue;
    if(mat[i]!=-1) continue;
    while(!Q.empty()) Q.pop();
    Q.push(i),pre[i]=-1,flg=0;
    while(!Q.empty() && !flg)
    {
      rg u=Q.front();Q.pop();
      for(rg j=Ehead[u];(j)&&(!flg);j=e[j].nxt)
      {
        rg v=e[j].to;
        if(vis[v]==i) continue; 
        vis[v]=i;
        if(mat[v]>=0)  pre[mat[v]]=u,Q.push(mat[v]);
        else
        {
          flg=1;
          rg a=u,b=v;
          while(a!=-1)
          {
            rg c=mat[a];
            mat[a]=b;
            mat[b]=a;
            a=pre[a];
            b=c;
          }
        }
       }
    }
  if(mat[i]!=-1) Ans++; 
  }
  return Ans;    
}
// 连边 case1: 认识在学校的人 
//      case2: 在学校且不离开,跟自己连 

bool DFS(int x)
{
       for(int i=Ehead[x];i;i=e[i].nxt)
       {
              int v=e[i].to;
              if(!vis[v])
              {
                    vis[v]=true;
                    if(!mat[v]||DFS(mat[v]))
                    {
                            mat[v]=x;
                            return true;
                    }
              }
       }
       return false;
}

il void work()
{
  memset(Ehead,0,sizeof(Ehead)),Ecnt=1;
  n=GI();
  RG tot=0;  //统计需要床的总人数
  for(RG i=1;i<=n;++i) 
  {
    I[i]=GI();  
    if( !I[i] )
     ++tot;  // 不在学校的人需要床
  }
  for(RG i=1;i<=n;++i) 
  {
    J[i]=GI();
    if( !J[i] && I[i] ) 
     Eadd(i,i) , ++tot;  //留校生 也需要床 并且自己的床也可以睡
  }
  for(RG i=1;i<=n;++i)
   for(RG j=1;j<=n;++j)
   {
      RG IN=GI();
      if( IN && I[j] ) //认识 并且那人在学校 就可以睡
       Eadd(i,j);
   }   
         /*      memset(mat,0,sizeof(mat));
              RG sum=0;
             for(int i=1;i<=n;++i)
             {
                   if((I[i]&&J[i]==0)||!I[i])//要么是学生在学校，要么是外来的人
                   {
                         memset(vis,0,sizeof(vis));
                         if(DFS(i))++sum;
                   }
             }*/
  if(Hung()==tot) cout<<"^_^\n";
  else cout<<"T_T\n";
}
int main()
{
  RG T=GI();
  while(T--) work();
  return 0;
}