9. ნუსხა ტესტის დროს პროფესორ ფლოიდმა შენიშნა, რომ ზოგიერთი სტუდენტი ჩანაწერებს ცვლიდა. თავდაპირველად, ის ყველა სტუდენტს აძლევდა მეორე ქულას, მაგრამ პროფესორი კეთილი იყო და გადაწყვიტა სტუდენტები ორ ჯგუფად დაყო: მათ, ვინც ნუსხის ასაღებად ნებართვას აძლევდა, და პირველ ჯგუფს მხოლოდ მეორე ქულას აძლევდა. პროფესორმა ყველა სტუდენტის ცვლილი წყვილი დააფიქსირა. აუცილებელია განსაზღვრო, თუ შესაძლებელია სტუდენტების დაყოფა ორ ჯგუფად ისე, რომ ნებისმიერი ჩანაწერის გაცვლა მოხდეს ერთ ჯგუფის სტუდენტიდან მეორეზე. შესავალი ფორმატი პირველ ხაზზე განთავსებულია ორი რიცხვი 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", значит профессор сможет разделить студентов на две группы, иначе — нет.