Ответ:Для решения этой задачи можно использовать топологическую сортировку на графе, где вершины представляют игроков, а ребра соответствуют парам игроков, в которых первый игрок всегда побеждает второго. Если такой граф содержит цикл, то провести турнир в соответствии с заданными парами игроков невозможно, так как в цикле каждый игрок побеждает следующего, а последний игрок побеждает первого, что противоречит условию, что должен остаться только один победитель. Если же граф не содержит циклов, то топологическая сортировка позволит упорядочить вершины в порядке, в котором можно провести турнир так, чтобы победитель всех матчей был известен заранее и в конце остался только один игрок.

Для реализации этого алгоритма нужно сначала построить граф, а затем применить к нему топологическую сортировку. Если в результате сортировки была получена последовательность вершин, то турнир можно провести согласно этой последовательности. Если же был обнаружен цикл, то турнир провести невозможно.

Ниже приведена реализация алгоритма на языке Python:

from collections import defaultdict

n, m = map(int, input().split())

graph = defaultdict(list)

in_degree = [0] * (n + 1)

# Построение графа

for _ in range(m):

   a, b = map(int, input().split())

   graph[b].append(a)

   in_degree[a] += 1

# Топологическая сортировка

result = []

queue = [i for i in range(1, n + 1) if in_degree[i] == 0]

while queue:

   u = queue.pop(0)

   result.append(u)

   for v in graph[u]:

       in_degree[v] -= 1

       if in_degree[v] == 0:

           queue.append(v)

# Проверка наличия цикла

if len(result) != n:

   print("No")

else:

   print("Yes")

   for i in range(n - 1):

       print(result[i], result[i + 1])

Алгоритм имеет временную сложность O(N+M), где N — количество игроков, а M — количество пар игроков, в которых первый игрок всегда побеждает второго.

Объяснение: