Bipartite Graph Check

Given an undirected graph represented by an adjacency matrix, determine whether the graph is bipartite. A graph is bipartite if its vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex from the other set. In mathematical terms, for a graph \(G=(V, E)\), there exists a partition \(V = V_1 \cup V_2\) with \(V_1 \cap V_2 = \emptyset\) such that every edge \((u,v) \in E\) satisfies \(u \in V_1, v \in V_2\) (or vice versa).

The input graph may be disconnected. Your task is to determine whether the graph can be colored using two colors (for example, color 0 and color 1) such that no adjacent vertices share the same color. Output "YES" if it is bipartite and "NO" otherwise.

inputFormat

The first line contains an integer \(n\) representing the number of vertices in the graph. The following \(n\) lines each contain a string of length \(n\) consisting of '0's and '1's. The \(j\)-th character of the \(i\)-th string indicates whether there is an edge between vertex \(i\) and vertex \(j\) (a '1' denotes an edge, while '0' denotes no edge).

outputFormat

Output a single line containing "YES" if the graph is bipartite, and "NO" otherwise.

3
011
101
110

NO