Problem E
Monopol

Jocke och hans vänner brukar spela Monopol med varandra. Men efter otaliga spel har de tröttnat på de vanliga reglerna, och har därför ändrat på dem en aning:

Först väljer de ett lagom stort land. De tar sedan en titt på vägnätet i landet och väljer ut ett antal städer som bildar en cykel (som på ett monopolbräde). Därefter åker de till landet, och spelar genom att åka runt cykeln i sina bilar och köper/säljer fastigheter med riktiga pengar.

Det finns dock en begränsning som gör det svårt att genomföra spelet: de måste hitta en lämplig cykel i vägnätet. Vissa länder har nämligen väldigt stora vägnät. Något som försvårar ytterligare är att cykeln måste ha ett jämnt antal kanter, för annars funkar inte reglerna (“Fri parkering” hamnar inte i mitten vilket ger ett obalanserat spel).

Du får givet en oriktad graf, och din uppgift är att hitta en cykel med ett jämnt antal kanter, om det finns en.

   

Figure 1: Illustration av graferna i de tre exempelfallen.

Indata

Den första raden innehåller två heltal $N$ och $M$, antalet noder respektive antalet kanter ($1\le N \le 10^5$, $0\le M \le \mathrm{min}(2\cdot 10^5, \tfrac {n(n-1)}{2})$).

Sedan följer $M$ rader med två heltal $a$ och $b$ vardera, vilket betyder att det finns en kant mellan noderna $a$ och $b$ i grafen ($1\le a, b \le N$ och $a\neq b$). Det är garanterat att det inte finns flera kanter mellan samma par av noder i grafen.

Utdata

Om det inte finns en jämn cykel, skriv ut en rad med strängen “NO”.

Om det finns en jämn cykel, skriv ut en rad med strängen “YES”. Därefter ska du skriva ut en sådan cykel. Skriv först ut en rad med ett jämnt heltal $k$ ($4\le k \le N$), antalet noder i din cykel. På nästa rad, skriv ut $K$ stycken olika heltal $v_{1}, v_{2}, \ldots , v_{k}$ ($1\le v_{i}\le N$) separerade av mellanslag: noderna på din cykel, så att kanterna $(v_{1},v_{2}), (v_{2},v_{3}),\ \ldots , (v_{k-1},v_{k}), (v_{k}, v_{1})$ finns i grafen.

Om det finns flera möjliga svar så kommer vilket som helst accepteras.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Notera att vissa exempelfall inte är giltiga i vissa testfallsgrupper.

Exempelfall

4 5
1 2
1 3
2 3
3 4
4 1

YES
4
3 2 1 4 

5 6
1 2
1 3
1 4
1 5
2 3
4 5

NO

7 6
1 7
3 4
4 5
5 6
6 3
5 2

YES
4
6 3 4 5