Graph Coloring Check with Three Colors

You are given an undirected graph with n vertices and m edges. You have three distinct colors available. Determine whether it is possible to color the graph using these three colors such that no two adjacent vertices share the same color.

Note that the intended solution checks if the graph is bipartite. In other words, if the graph can be colored using only two colors then the answer is Yes (since the third color remains unused), otherwise the answer is No. For example, a triangle (3-cycle) is not bipartite even though it can be colored with three different colors; hence the expected output is No.

This is a simplified variant of a graph coloring problem and can be solved efficiently by checking bipartiteness using BFS (or DFS).

inputFormat

The first line of input contains two integers n and m (1 ≤ n ≤ 10^5, 0 ≤ m ≤ 10^5), representing the number of vertices and edges respectively. The following m lines each contain two integers u and v (1 ≤ u, v ≤ n), representing an undirected edge between vertex u and vertex v.

outputFormat

Output a single line containing Yes if it is possible to color the graph under the given constraints, or No otherwise.## sample

3 3
1 2
2 3
3 1

No