Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Little Q loves playing with different kinds of graphs very much. One day he thought about an interesting category of graphs called ``Cool Graph'', which are generated in the following way:

Let the set of vertices be {1, 2, 3, ..., $n$}. You have to consider every vertice from left to right (i.e. from vertice 2 to $n$). At vertice $i$, you must make one of the following two decisions:

(1) Add edges between this vertex and all the previous vertices (i.e. from vertex 1 to $i-1$).

(2) Not add any edge between this vertex and any of the previous vertices.

In the mathematical discipline of graph theory, a matching in a graph is a set of edges without common vertices. A perfect matching is a matching that each vertice is covered by an edge in the set.

Now Little Q is interested in checking whether a ''Cool Graph'' has perfect matching. Please write a program to help him.

Let the set of vertices be {1, 2, 3, ..., $n$}. You have to consider every vertice from left to right (i.e. from vertice 2 to $n$). At vertice $i$, you must make one of the following two decisions:

(1) Add edges between this vertex and all the previous vertices (i.e. from vertex 1 to $i-1$).

(2) Not add any edge between this vertex and any of the previous vertices.

In the mathematical discipline of graph theory, a matching in a graph is a set of edges without common vertices. A perfect matching is a matching that each vertice is covered by an edge in the set.

Now Little Q is interested in checking whether a ''Cool Graph'' has perfect matching. Please write a program to help him.

The first line of the input contains an integer $T(1\leq T\leq50)$, denoting the number of test cases.

In each test case, there is an integer $n(2\leq n\leq 100000)$ in the first line, denoting the number of vertices of the graph.

The following line contains $n-1$ integers $a_2,a_3,...,a_n(1\leq a_i\leq 2)$, denoting the decision on each vertice.

In each test case, there is an integer $n(2\leq n\leq 100000)$ in the first line, denoting the number of vertices of the graph.

The following line contains $n-1$ integers $a_2,a_3,...,a_n(1\leq a_i\leq 2)$, denoting the decision on each vertice.

提交代码