9. Nüsxə alma İmtahanda, professor Floyd bəzi tələbələrin qeydlərini dəyişdiyini müşahidə etdi. Əvvəlcə, o, hamısına 2 qiymət qoymaq istəyirdi, amma professor mehriban idi və tələbələri iki qrupa bölməyə qərar verdi: nüsxə icazəsi verənlər və yalnız ilk qrupa 2 qiymət qoyanlar. Professor bütün tələbələr arasında qeydlərini dəyişən cütlükləri qeyd etdi. Tələbələri iki qrupa bölmək mümkün olub-olmadığını müəyyən etmək lazımdır ki, hər bir qeydlər mübadiləsi bir qrup tələbəsindən digər qrupa tələbəyə həyata keçirilsin. Daxil etmə formatı İlk sətirdə iki ədəd N və M yerləşir — tələbə sayı və qeydlərini dəyişən tələbələr cütlüklərinin sayı (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Sonra, M sətirdə, tələbələr cütlüklərinin təsviri verilir: qeydlərini dəyişən tələbələrin nömrələri (tələbə nömrələməsi 1-dən başlayır, hər cütlük bir dəfə qeyd olunur). Çıxış formatı Professor Floyd-un vəzifəsinə cavab yazılmalıdır. Əgər tələbələri iki qrupa bölmək mümkün olarsa, YES yazın; əks halda, 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", значит профессор сможет разделить студентов на две группы, иначе — нет.