P2055 [ZJOI2009] Dormitory During the Holidays

The school is on vacation. Some students go home, while some of their old friends come to visit, so accommodation becomes a problem. For example, A and B are both students of the school. A is going home, and C comes to visit B. C and A do not know each other. We assume each person can only sleep in the bed of someone they know directly. Then one solution is: B sleeps in A’s bed, and C sleeps in B’s bed. In reality, things can be much more complicated: some people may know many students who are on campus, and students on campus may not all know each other. We know there are $n$ people in total, and for each person we know whether they are a student of this school, and for each student we know whether they will go home. Determine whether there exists an arrangement such that all students who do not go home and all the other people who come to visit them have a place to stay.

The first line contains an integer $T$ denoting the number of test cases. Then follow $T$ test cases. For each test case, the first line contains an integer $n$ denoting the total number of people involved. The next line contains $n$ numbers; the $i$-th number indicates whether person $i$ is a student of the school ($0$ means no, $1$ means yes). The next line contains $n$ numbers; the $i$-th number indicates whether person $i$ will go home ($0$ means not going home, $1$ means going home; note that if person $i$ is not a student, the number at this position is random and should be ignored after reading). Then follow $n$ lines, each with $n$ numbers. The number in row $i$, column $j$ indicates whether $i$ and $j$ know each other ($1$ means yes, $0$ means no; the value at row $i$, column $i$ is $0$, but of course everyone can still sleep in their own bed). The acquaintance relationship is mutual.

For each test case, output `^_^` if a valid arrangement exists; otherwise, output `T_T`. Note that the outputs must be half-width characters (ASCII).

For $30\%$ of the testdata, $1 \le n \le 12$. For $100\%$ of the testdata, $1 \le n \le 50$, $1 \le T \le 20$. Translated by ChatGPT 5