Bipartite Graph Check.

Check if a given graph is bipartite.


A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

The two sets U and V may be thought of as a coloring of the graph with two colors: if one colors all nodes in U blue, and all nodes in V green, each edge has endpoints of differing colors, as is required in the graph coloring problem. In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle: after one node is colored blue and another green, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color.


Approach:
1. Starting from a vertex S (0th level), assign S, the color 1 (say 1 means red);
2. do a level order traversal, ie do a Breadth First Search.
3. the nodes which are 1-degree aways from S, ie on 1st level, assign them color 2 (2 stands for green).
4. At any point during BFS, if going from U to V, we are not able to assign V color different from U then its not bipartite.
5. If BFS is done and every level L is of different color than level L-1 then its bipartite.




Input:
first line contains the number of nodes
then n (number of nodes) rows follow depicting the list of nodes connected to a node X. - this is adjacency list representation.


A B C D -> number of nodes.
A B D -> node A is connected to B and D.
B A C D -> node B is connected to A, C and D.
C B D -> node C is connected to B and D.
D A C B -> node D is connected to A, C and B.
Is Bipartite: false 


Another example input/output:
A B C D
A B D
B A C 
C B D
D A C
Is Bipartite: true