Кіріспе формат Бірінші жолда студенттердің саны N және ноталар алмасқан жұптардың саны M көрсетіледі (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Келесі M жолда ноталар алмасқан студенттердің жұптарының сипаттамалары беріледі: екі сан, ноталар алмасқан студенттердің нөмірлері (студенттердің нөмірі 1-ден басталады, әр жұп бір реттен артық көрсетілмеген). Шығыс формат Профессор Флойдтың тапсырмасына жауап беру керек. Егер студенттерді екі топқа бөлу мүмкін болса - YES, ал болмаса - NO.

Задача сводится к проверке, можно ли разбить множество студентов на две группы так, чтобы все пары обмена записками были между студентами из разных групп. Это классическая задача проверки двудольности графа.

Алгоритм решения:

1. Представить студентов как вершины графа, а пары обмена записками — как рёбра.
2. Попытаться раскрасить граф в два цвета (например, 0 и 1), так чтобы соседние вершины имели разные цвета.
3. Если при обходе графа (DFS или BFS) возникает конфликт (ребро между вершинами одного цвета), значит разделить нельзя.

Пример на 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")

Если вывод "YES", значит профессор сможет разделить студентов на две группы, иначе — нет.