- Time limit: 1.00 s
- Memory limit: 512 MB
Annettuna on suuntaamaton verkko, jossa on solmua ja kaarta.
Sinun tulee valita jokaiselle kaarelle suunta niin, että tuloksena on suunnattu verkko. Valinnan jälkeen saat jokaisen solmun kohdalla sakkoa , missä on solmuun tulevien kaarten määrä ja on solmusta lähtevien kaarten määrä.
Tehtäväsi on valita suunnat niin, että yhteissakko on mahdollisimman pieni. Miten menettelet?
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua ja : solmujen ja kaarten määrä. Solmut on numeroitu .
Tämän jälkeen syötteessä on riviä, jotka kuvaavat kaaret. Jokaisella rivillä on kaksi kokonaislukua ja : solmujen ja välillä on kaari.
Voit olettaa, että jokainen kaari yhdistää kaksi eri solmua ja jokaisen kahden solmun välillä on enintään yksi kaari.
Tuloste
Tulosta ensin yksi kokonaisluku: pienin mahdollinen yhteissakko.
Tulosta sitten riviä, jotka kuvaavat kaarten suunnat ratkaisussasi. Jokainen rivi tarkoittaa, että kaari alkaa vasemmasta solmusta ja päättyy oikeaan solmuun.
Voit tulostaa minkä tahansa kelvollisen ratkaisun ja kaaret missä tahansa järjestyksessä.
Rajat
Esimerkki
Syöte:
4 4 1 2 2 3 1 3 3 4
Tuloste:
2 3 4 1 3 3 2 2 1
Selitys: Ratkaisussa solmujen ja sakko on ja solmujen ja sakko on , joten kokonaissakko on .