Game Scheduling with Restricted Matches

You are given N players numbered from 1 to N and M restricted pairs. Each restricted pair indicates that the two players cannot be scheduled together in the same game. The goal is to determine whether it is possible to create a schedule in which the players can be divided into two groups (teams) such that no restricted pair is on the same team.

This is equivalent to checking whether the undirected graph \(G=(V,E)\) formed by players as vertices and restricted pairs as edges is bipartite. In other words, there exists a partition of the vertex set \(V = V_1 \cup V_2\) such that for every edge \((u,v) \in E\), we have \(u \in V_1\) and \(v \in V_2\) (or vice versa).

If such a partition exists, output YES; otherwise, output NO.

inputFormat

The input is read from stdin and has the following format:

N M
u1 v1
u2 v2
...
uM vM

Here, the first line contains two integers N and M representing the number of players and the number of restricted pairs respectively. Each of the next M lines contains two integers \(u\) and \(v\) indicating that players \(u\) and \(v\) cannot be scheduled on the same team.

outputFormat

Output a single line to stdout containing either YES if it is possible to schedule the games by dividing the players into two teams such that no restricted pair is on the same team, or NO otherwise.

4 2
1 2
3 4

YES