Taco Time Slot Assignment

You are organizing a series of contests and need to assign one of three available time slots (labeled 0, 1, and 2) to each contest. However, there are constraints: certain pairs of contests cannot have time slots that conflict with a forced assignment rule. Specifically, when assigning a time slot using the following rule, for any contest u with assigned time slot c, every unassigned contest v that is constrained with u must be assigned the time slot \( (c+1) \mod 3 \). If a contest is already assigned a slot, it must be consistent with this rule for all constraints.

Your task is to determine whether it is possible to assign time slots to all contests following this forced rule without any conflicts. If an assignment is possible, print YES. Otherwise, print NO.

Note: The assignment is done using a breadth-first search (BFS) approach. For each unvisited contest, assign it slot 0 and then assign each of its neighbors the slot that is one more (modulo 3) than the current contest's slot. If a conflict arises (i.e. a neighbor has the same slot as the current contest), then the assignment is not possible.

inputFormat

The first line of input contains two space-separated integers \( k \) and \( m \), representing the number of contests and the number of constraints, respectively. The next \( m \) lines each contain two integers \( u \) and \( v \) (1-indexed), indicating that contest \( u \) and contest \( v \) cannot share time slots under the forced assignment rule.

outputFormat

Output a single line containing YES if it is possible to assign time slots to all contests following the forced rule. Otherwise, output NO.

3 2
1 2
2 3

YES