Bipartite Graph Verification

You are given an undirected graph with N nodes and M edges. Your task is to determine whether the graph is bipartite or not.

A graph is bipartite if its set of vertices can be divided into two disjoint subsets such that no two vertices within the same subset are adjacent. In mathematical notation, a graph G = (V, E) is bipartite if there exists a partition V = V₁ \cup V₂ such that for every edge (u, v) ∈ E, either u ∈ V₁ and v ∈ V₂ or u ∈ V₂ and v ∈ V₁.

If the graph is bipartite, output 1; otherwise, output 0.

Note: The graph might be disconnected. You must check each connected component.

inputFormat

The first line of input contains two integers N and M representing the number of nodes and the number of edges, respectively.

The next M lines each contain two integers u and v indicating an undirected edge between nodes u and v.

It is guaranteed that 1 ≤ u, v ≤ N.

outputFormat

Output a single integer: 1 if the graph is bipartite, otherwise 0. The output should be printed to stdout.

4 4
1 2
2 3
3 4
4 1

1