9. Cheating During a test, Professor Floyd noticed some students exchanging notes. Initially, he wanted to give them all failing grades, but the professor was kind and decided to divide students into two groups: those who cheat and those who get failing grades only first. The professor has recorded all pairs of students exchanging notes. You need to determine if he can divide students into two groups so that any note exchange occurs between a student of one group and a student of the other group. Input format The first line contains two numbers N and M — the number of students and the number of pairs exchanging notes (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Next, M lines contain descriptions of pairs of students: two numbers corresponding to the student numbers exchanging notes (student numbering starts from 1, each pair is listed no more than once). Output format You need to output the answer to Professor Floyd's problem. If it is possible to divide students into two groups, output YES; otherwise, NO.

The task reduces to checking whether it is possible to split the set of students into two groups such that all note exchange pairs are between students from different groups. This is a classic problem of checking bipartiteness of a graph.

Solution algorithm:

1. Represent students as vertices of a graph, and note exchange pairs as edges.
2. Try to color the graph with two colors (for example, 0 and 1), so that adjacent vertices have different colors.
3. If during a graph traversal (DFS or BFS) a conflict arises (an edge between vertices of the same color), then it is not possible to split.

Example in Python:

from collections import deque

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u-1].append(v-1)
    graph[v-1].append(u-1)

color = [-1] * N

def bfs(start):
    queue = deque([start])
    color[start] = 0
    while queue:
        u = queue.popleft()
        for w in graph[u]:
            if color[w] == -1:
                color[w] = 1 - color[u]
                queue.append(w)
            elif color[w] == color[u]:
                return False
    return True

is_bipartite = True
for i in range(N):
    if color[i] == -1:
        if not bfs(i):
            is_bipartite = False
            break

print("YES" if is_bipartite else "NO")

If the output is "YES", then the professor can divide the students into two groups; otherwise, he cannot.