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", значит профессор сможет разделить студентов на две группы, иначе — нет.