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