Annettuna on suunnattu verkko, jossa on n solmua ja m kaarta. Verkossa ei ole syklejä, eli mistään solmusta ei pääse kaaria pitkin takaisin samaan solmuun.

Tehtäväsi on selvittää, voiko verkkoon muodostaa kaksi polkua niin, että jokainen verkon solmu esiintyy täsmälleen yhdessä polussa. Huomaa, että kaikkien verkon kaarien ei tarvitse esiintyä poluissa.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja m: solmujen määrä ja kaarten määrä. Solmut on numeroitu 1,2,\dots,n.

Tämän jälkeen tulee m riviä, jotka kuvaavat kaaret. Jokaisella rivillä on kaksi kokonaislukua a ja b: verkossa on kaari solmusta a solmuun b.

Tuloste

Tulosta ensin rivi YES, jos polut voi muodostaa, tai NO muuten.

Jos polut voi muodostaa, tulosta ne seuraavalle kahdelle riville. Tulosta kummankin rivin alkuun polun solmujen määrä ja tämän jälkeen polun solmut järjestyksessä. Peräkkäisten solmujen välillä on oltava kaari verkossa. Jos ratkaisuja on useita, voit tulostaa minkä tahansa ratkaisun.

Esimerkki 1

Syöte:

5 4
1 2
1 4
3 4
4 5

Tuloste:

YES
2 1 2
3 3 4 5

Esimerkki 2

Syöte:

5 4
1 2
1 3
1 4
1 5

Tuloste:

NO

Osatehtävä 1 (33 pistettä)

• 2 \le n \le 200
• 0 \le m \le 500

Osatehtävä 2 (33 pistettä)

• 2 \le n \le 10^4
• 0 \le m \le 2\cdot10^4

Osatehtävä 3 (34 pistettä)

• 2 \le n \le 2\cdot10^5
• 0 \le m \le 5\cdot 10^5