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

Теперь рассмотрим, какая компонента связности будет выигрышной. Можно доказать, что если в компоненте связности нечетное число ребер, первый игрок может выиграть. Для этого, сделаем лемму: В любом связном графе, содержащем нечетное число ребер, для любой вершины можно выбрать смежное с ней ребро, что после его удаления, во всех получившихся компонентах связности (одной или двух), число ребер будет четно. Назовем такое ребро хорошим.

Тогда, первому игроку нужно будет играть следующим образом:

1. Выбрать компоненту с нечетным числом ребер
2. Выбрать в этой компоненте любую вершину $$$v$$$
3. По лемме, выбрать в текущей компоненте из вершины $$$v$$$ любое хорошее ребро, и удалить его
4. Второй на своем ходу либо проигрывает, если не может сходить, либо удаляет ребро $$$(a, b)$$$
5. Если второй удалил ребро, он удалил его в компоненте с четным число ребер (по свойству хорошего ребра). И тогда возможны два случая:
   • Компонента, в которой находилось ребро $$$(a, b)$$$ осталась связна. Тогда там стало нечетное число ребер, и первый игрок выбирает в качестве вершины $$$v$$$ любую из вершин $$$a$$$ и $$$b$$$
   • Компонента, в которой находилось ребро $$$(a, b)$$$, распалась на две. Тогда ровно одна из двух получившихся компонент содержит нечетное число ребер. А $$$a$$$ и $$$b$$$ лежат в разных компонентах. Тогда в качестве $$$v$$$ первый игрок выберет из вершин $$$a$$$ и $$$b$$$ ту, которая лежит в компоненте с нечетным числом ребер
6. Переходим к пункту 3

Первый игрок не может проиграть, потому что на его ходу в текущей компоненте нечетное число ребер (и поэтому по лемме он может выбрать хорошее ребро).

Доказательство леммы:

• Если есть ребро, смежное $$$v$$$, которое не является мостом, удалим его. Тогда компонента не распадется, и значит в этой одной компоненте будут все ребра, кроме удаленного — четное число
• Остался случай, когда все ребра, ведущие из вершины — мосты. Пусть их k. Пойдем от противного: пусть ни одно из этих ребер не является хорошим. Тогда, после удаления любого ребра, в двух получившихся компонентах будет нечетное число ребер. Значит, в каждой из $$$k$$$ компонент, которые получаются, если удалить $$$v$$$ со всеми смежными с ней ребрами, будет нечетное число ребер. Тогда посчитаем количество ребер в исходном графе по модулю $$$2$$$: $$$k + \sum\limits_{i = 1}^{k} e_i \underset{2}{\equiv} k + \sum\limits_{i = 1}^{k} 1 \underset{2}{\equiv} k + k \underset{2}{\equiv} 0$$$ ($$$e_i$$$ — количество ребер в $$$i$$$-й компоненте). Противоречие.

Можно заметить, что второй случай покрывает в том числе случай, если степень вершины $$$v$$$ равна $$$1$$$.

Таким образом, чтобы решить задачу, нужно пройтись по всем компонентам связности, например обходом в глубину, и проверить есть ли среди них та, что содержит нечетное число ребер. Итоговая сложность решения O($$$n + m$$$).