Check Bipartite Graph

Given an undirected graph represented by an adjacency matrix of size n × n, determine if the graph is bipartite.

A graph is bipartite if its vertices can be divided into two disjoint sets \(U\) and \(V\) such that every edge connects a vertex in \(U\) to one in \(V\). In other words, the graph can be colored using two colors such that no two adjacent vertices share the same color. This can be expressed as:

\[ \forall (u,v) \in E, \quad color(u) \neq color(v) \]

The input graph is given as an adjacency matrix where each entry is either 0 or 1, the matrix is symmetric, and all diagonal elements are 0. It is guaranteed that \(1 \le n \le 100\).

Your task is to determine whether the given graph is bipartite.

inputFormat

The first line contains a single integer \(n\), the number of vertices in the graph.

Each of the next \(n\) lines contains \(n\) space-separated integers (0 or 1) representing a row of the adjacency matrix.

outputFormat

Output a single line: True if the graph is bipartite, and False otherwise.

## sample

4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

True