Bipartite Graph Checker

You are given several graphs represented by their adjacency matrices. A graph is bipartite if its vertex set can be partitioned into two disjoint subsets in such a way that every edge connects a vertex from one subset to a vertex from the other subset. In mathematical terms, a graph \( G = (V, E) \) is bipartite if there exists a function \( f: V \to \{0,1\} \) such that for every edge \( (u,v) \in E \), it holds that \( f(u) \neq f(v) \).

Your task is to determine whether each given graph is bipartite. For each graph, output "Yes" if the graph is bipartite, or "No" otherwise.

The input begins with a single integer \( T \) indicating the number of graphs. For each graph, an integer \( N \) (the number of vertices) is given, followed by \( N \) lines each containing \( N \) integers (either 0 or 1) representing the adjacency matrix of the graph. It is guaranteed that the diagonal elements of the matrix are 0.

inputFormat

The first line of input contains a single integer \( T \) (\(1 \leq T \leq 100\)), the number of graphs to check. This is followed by \( T \) test cases. For each test case:

• The first line contains an integer \( N \) (\(1 \leq N \leq 100\)), the number of vertices in the graph.
• The following \( N \) lines each contain \( N \) integers (each either 0 or 1), representing the rows of the adjacency matrix of the graph.

outputFormat

For each test case (graph), output a single line containing either "Yes" if the graph is bipartite, or "No" otherwise.

## sample

2
3
0 1 1
1 0 0
1 0 0
4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

Yes
Yes

</p>