CSES - Suunnat
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Annettuna on suuntaamaton verkko, jossa on nn solmua ja mm kaarta.

Sinun tulee valita jokaiselle kaarelle suunta niin, että tuloksena on suunnattu verkko. Valinnan jälkeen saat jokaisen solmun xx kohdalla sakkoa in(x)out(x)|\textrm{in}(x)-\textrm{out}(x)|, missä in(x)\textrm{in}(x) on solmuun tulevien kaarten määrä ja out(x)\textrm{out}(x) 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 nn ja mm: solmujen ja kaarten määrä. Solmut on numeroitu 1,2,,n1,2,\dots,n.

Tämän jälkeen syötteessä on mm riviä, jotka kuvaavat kaaret. Jokaisella rivillä on kaksi kokonaislukua aa ja bb: solmujen aa ja bb 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 mm 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

  • 1n21051 \le n \le 2 \cdot 10^5
  • 1m51051 \le m \le 5 \cdot 10^5

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 11 ja 22 sakko on 00 ja solmujen 33 ja 44 sakko on 11, joten kokonaissakko on 1+1=21+1=2.