Check if the Graph is Bipartite

A graph is considered bipartite if it’s possible to colorize it with two colors such that no two adjacent vertices have the same color.
Determining if a graph is bipartite can help identify specific structures and properties, enabling efficient problem-solving in domains such as scheduling, resource allocation, and conflict resolution. Bipartite graphs also allow for simpler algorithms and optimizations in tasks like maximum matching and graph coloring.
You are given an undirected graph with v vertices and e edges. You should check if the graph is bipartite or not.

Input

The first line of the input contains two integers v (1 ≤ v ≤ 100 000) and e (1 ≤ e ≤ 100 000).
The following e lines contain pairs of integers v1, v2 (1 ≤ v1, v2 ≤ v) which means that the vertex v1 is connected to the vertex v2 and vice versa.

Output

The program should print Yes if the given graph is bipartite and No otherwise.

Examples

Input
Output
2 1 2 1
Yes
3 2 2 1 1 3
Yes
3 3 1 2 1 3 2 3
No
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue