[ZJOI2009]假期的宿舍

学校放假了，有些同学回家了，而有些同学则有以前的好朋友来探访，因此住宿就成了一个问题。

例如， $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$ ，但每个人显然仍然可以睡在自己的床上。

对于每组数据，如果存在一种可行的住宿安排，则输出 ^_^；否则输出 T_T。

注意，输出的均为半角字符。

^_^

本题为 ZJOI 2009 试题「假期的宿舍」，题面与测试数据整理自 BZOJ。

^_^