题目描述 （模板题）

注：题目可在牛客竞赛OJ找到尝试提交

学校放假了······有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。比如A和B都是学校的学生，A要回家，而C来看B，C与A不认识。我们假设每个人只能睡和自己直接认识的人的床。那么一个解决方案就是B睡A的床而C睡B的床。

而实际情况可能非常复杂，有的人可能认识好多在校学生，在校学生之间也不一定都互相认识。我们已知一共有n个人，并且知道其中每个人是不是本校学生，也知道每个本校学生是否回家。

问是否存在一个方案使得所有不回家的本校学生和来看他们的其他人都有地方住。

输入描述:

第一行一个数T表示数据组数。接下来T组数据，
每组数据第一行一个数n表示涉及到的总人数。
接下来一行n个数，第i个数表示第i个人是否是在校学生(0表示不是，1表示是)。
再接下来一行n个数，第i个数表示第i个人是否回家
(0表示不回家，1表示回家，注意如果第i个人不是在校学生，那么这个位置上的数是一个随机的数，
你应该在读入以后忽略它)。
接下来n行每行n个数，
第i行第j个数表示i和j是否认识
(1表示认识，0表示不认识，第i行i个的值为0，但是显然自己还是可以睡自己的床)，
认识的关系是相互的。
1 ≤ n ≤ 50,1 ≤ T ≤ 20

输出描述:

对于每组数据，如果存在一个方案则输出“^_^”(不含引号)否则输出“T_T”(不含引号)。
(注意输出的都是半角字符，即三个符号的ASCII码分别为94,84,95)

示例1

输入

复制;)

1
3
1 1 0
0 1 0
0 1 1
1 0 0
1 0 0

输出

复制;)

^_^

备注:

对于 30% 的数据满足 1 ≤ n ≤ 12。
对于 100% 的数据满足 1 ≤ n ≤50, 1 ≤ T ≤ 20。

题目分析：

这是一道二分图最大匹配的模板题，读完题我们可以很快看出来，人和床构成二分图的两个集合，只要来访的人和留校学生都能和一张床进行匹配就满足条件。

python code：

import sys

"""邻接表做法"""
def solve():
    n = int(sys.stdin.readline())
    stu = [0]+list(map(int, sys.stdin.readline().split()))
    ishui = [0]+list(map(int, sys.stdin.readline().split()))
    g = {i:[] for i in range(n+1)}
    for i in range(1,n+1):
        g[i].append(i)
    for i in range(1,n+1):
        tmp = list(map(int, sys.stdin.readline().split()))
        for j in range(n):
            if tmp[j] == 1:
                g[i].append(j+1)
    
    def dfs(x):
        for y in g[x]:
            if vis[y] or not stu[y]: continue
            vis[y] = True
            if not link[y] or dfs(link[y]):
                link[y] = x
                return True
        return False
    
    ans = 0
    link = [0]*(n+1)
    for i in range(1,n+1):
        vis = [0]*(n+1)
        if not stu[i] or (stu[i] and not ishui[i]):
            if not dfs(i):
                print("T_T")
                return
    print("^_^")
    
for _ in range(int(sys.stdin.readline())):
    solve()