Wie löse ich das folgende Grafikspiel?

Betrachten Sie das folgende Spiel in einem ungerichteten Graphen G. Es gibt zwei Spieler, einen roten Spieler R und einen blauen Spieler B. Anfangs sind alle Kanten von G ungefärbt. Die zwei Spieler färben abwechselnd eine ungefärbte Kante von G mit ihrer Farbe, bis alle Kanten gefärbt sind. Das Ziel von B ist, dass am Ende die blau gefärbten Kanten einen verbundenen aufspannenden Teilgraphen von G bilden. Ein zusammenhängender aufspannender Teilgraph von G ist ein verbundener Teilgraph, der alle Ecken von Graph G enthält. Das Ziel von R ist, B zu verhindern vom Erreichen seines Ziels.

Angenommen, R startet das Spiel. Angenommen, beide Spieler spielen auf die klügste Art und Weise. Ihre Aufgabe ist es herauszufinden, ob B das Spiel gewinnt.

Eingabe: Jeder Testfall beginnt mit einer Zeile aus zwei ganzen Zahlen n (1 & lt; = n & lt; = 10) und m (0 & lt; = m & lt; = 30), wobei die Anzahl der Eckpunkte und Kanten in dem Graphen angezeigt wird. Alle Scheitelpunkte sind von 0 bis n-1 nummeriert. Dann folgen m Linien. Jede Zeile enthält zwei ganze Zahlen p und q (0 & lt; = p, q & lt; n), was anzeigt, dass eine Kante zwischen dem Vertex p und dem Vertex q vorhanden ist.

Ausgabe: Für jeden Testfall drucke eine Zeile aus, die entweder "JA" oder "NEIN" bedeutet, B wird das Spiel gewinnen oder nicht.

Beispiel:

3 4

0 1

1 2

2 0

0 2

Ausgabe: Ja

Meine Idee: Wenn wir zwei disjunkte Spannbäume des Graphen finden, gewinnt Spieler B das Spiel. Andernfalls gewinnt A. 'Zwei disjunkt überspannende Bäume' bedeutet, dass die Kantensätze der beiden Bäume disjunkt sind

Ich frage mich, ob Sie meine Idee beweisen oder widerlegen können