- Language:
- Time limit: 1.00 s
- Memory limit: 512 MB
Annettuna on suunnattu verkko, jossa on solmua ja 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 ja : solmujen määrä ja kaarten määrä. Solmut on numeroitu .
Tämän jälkeen tulee riviä, jotka kuvaavat kaaret. Jokaisella rivillä on kaksi kokonaislukua ja : verkossa on kaari solmusta solmuun .
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