Bipartite Graph Verification

You are given an undirected graph represented by its adjacency matrix. Your task is to determine whether the graph is bipartite.

A graph \(G = (V, E)\) is bipartite if its vertex set \(V\) can be partitioned into two disjoint subsets \(V_1\) and \(V_2\) such that every edge in \(E\) connects a vertex in \(V_1\) to a vertex in \(V_2\). Equivalently, the graph does not contain any odd-length cycles.

The graph is provided as an \(n \times n\) matrix, where the element in the \(i\)-th row and \(j\)-th column is 1 if there is an edge between vertex \(i\) and vertex \(j\), and 0 otherwise.

Your task is to output "Yes" if the graph is bipartite, and "No" otherwise.

inputFormat

The input is given via standard input (stdin) with the following format:

• The first line contains an integer \(T\), the number of test cases.
• For each test case, the first line contains an integer \(n\) representing the number of vertices.
• This is followed by \(n\) lines, each containing \(n\) space-separated integers (either 0 or 1) representing the adjacency matrix of the graph.

outputFormat

For each test case, print a single line containing either Yes if the graph is bipartite or No if it is not. The output should be printed to standard output (stdout).

## sample

1
3
0 1 0
1 0 1
0 1 0

Yes

</p>