Ставки перед началом тараканьих бегов были предложены всем болельщикам в виде двух ставок на результаты бегов. Каждая

обозначают количество тараканов и количество ставок (1 ≤ a, b ≤ 1000). Далее вводится b строк, каждая из которых содержит два различных числа xi и yi (1 ≤ xi, yi ≤ a) - номера тараканов в i-й ставке.

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

1. Прочитаем входные данные и создадим граф, где вершины представляют собой тараканов, а ребра - ставки. Для этого создадим пустой граф с a вершинами.

2. Для каждой ставки добавим направленное ребро от таракана xi к таракану yi. Это означает, что в данной ставке таракан xi должен прийти раньше, чем таракан yi.

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

3.1. Сначала найдем все вершины графа, у которых нет входящих ребер (т.е. ни одна ставка не зависит от данного таракана).

3.2. Удалим эти вершины из графа и соответствующие ребра. Если при этом удалось удалить хотя бы одну вершину, то продолжим с шага 3.1.

3.3. Если после всех удалений остались вершины в графе, значит, невозможно такое расположение тараканов, чтобы каждый болельщик выиграл только одну ставку.

3.4. Если после удаления всех вершин граф оказался пустым, значит, существует возможность такого расположения тараканов.

4. Выведем ответ на основе результата выполнения алгоритма. Если граф был пустым, выведем "YES", иначе - "NO".

Давайте рассмотрим пример входных данных:

Входные данные:
4 4
1 2
2 3
3 4
4 1

1. Создаем граф с 4 вершинами.

2. Добавляем ребра для каждой ставки:
- В ставке 1 таракан 1 должен прийти раньше таракана 2.
- В ставке 2 таракан 2 должен прийти раньше таракана 3.
- В ставке 3 таракан 3 должен прийти раньше таракана 4.
- В ставке 4 таракан 4 должен прийти раньше таракана 1.

3. Применяем топологическую сортировку:
- Удаляем вершины без входящих ребер: 1.
- Возвращаемся к шагу 3.1.

- Удаляем вершины без входящих ребер: 2, 3, 4.
- Граф пустой.

4. Выводим ответ "YES", так как существует возможность такого расположения тараканов.

На этом наше решение задачи завершается. Будьте уверены, что каждый болельщик сможет понять весь процесс решения и обоснование ответа. Если у вас возникнут дополнительные вопросы, не стесняйтесь задавать. Желаю успехов в обучении!