Bipartite Graph Check

Problem statement

An event planner assigns participants to two rooms. Certain pairs must be separated, and a participant can belong to only one room. The planner needs to know whether all separation requirements can be satisfied together. Your task Determine whether the undirected graph is bipartite: vertices can be split into two groups so that every edge joins different groups. Important details Either group may be empty when the graph has no edges. Disconnected components can choose their colors independently. An odd cycle prevents a valid split, whereas an even cycle does not. Output feasibility rather than a specific grouping. Worked example A four-cycle 0-1-2-3-0 can place {0, 2} in one room and {1, 3} in the other, giving true.

Input format

First line: n m. Next m lines: endpoints u v of undirected edges. Vertices are numbered 0 through n-1.

Output format

Print true if the condition holds, otherwise false.

Constraints

1 <= n <= 2000; 0 <= m <= 10000; endpoints are valid, with no self-loops or repeated edges.

Sample input

4 4
0 1
1 2
2 3
3 0

Sample output

true