Рассмотрим следующую игру на неориентированном графе G. Есть два игрока, игрок красного цвета R и игрок синего цвета B. Изначально все ребра G неокрашены.Два игрока поочередно окрашивают неокрашенный край G своим цветом, пока все края не будут окрашены.Цель B состоит в том, что в конце синие ребра образуют связный остовный подграф G. Связный остовный подграф G является связным подграфом, который содержит все вершины графа G. Целью R является предотвращение Bот достижения своей цели.
Предположим, что R запускает игру.Предположим, что оба игрока играют умнее.Ваша задача - выяснить, победит ли B в игре.
Входные данные: каждый тестовый пример начинается с строки из двух целых чисел n (1 <= n <= 10) и m (0 <= m <=30), с указанием количества вершин и ребер в графе.Все вершины пронумерованы от 0 до n-1.Затем следуют m строк.Каждая строка содержит два целых числа p и q (0 <= p, q <n), что указывает на наличие ребра между вершиной p и вершиной q.</p>
Вывод: для каждого тестового примера выведите строку «YES» или «NO», указывающую, выиграет игра или нет.
Пример:
3 4
0 1
1 2
2 0
0 2
Вывод: Да
Моя идея:Если мы можем найти два непересекающихся остовных дерева графа, то игрок B выигрывает игру.В противном случае победит.«Два непересекающихся остовных дерева» означают, что наборы ребер двух деревьев не пересекаются
Интересно, сможете ли вы доказать или опровергнуть мою идею