Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_2018_3e1_virsininkai.in

Rezultatų failas: lmio_2018_3e1_virsininkai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Viršininkai

Bendrovėje „Ūbr“ dirba N programuotojų. Jiems priskirti kodai – sveikieji skaičiai nuo 1 iki N. Visų darbuotojų kodai skirtingi.

Bendrovė vykdo M projektų. Už kiekvieną iš jų atsakingi du programuotojai ir tas, kurio kodas mažesnis, yra kito viršininkas. Žinoma, kad jokia darbuotojų pora nedirba prie daugiau nei vieno bendro projekto.

1 pav. Šiame pavyzdyje N=6 ir yra vykdomi penki projektai. Antras, trečias ir šeštas programuotojai turi po vieną viršininką, o ketvirtas programuotojas – du viršininkus.

„Ūbr“ nustatė, kad programuotojai, turintys daugiau nei vieną viršininką, mažiau mėgaujasi darbu. Bendrovė nori persitvarkyti, kad kiekvienas darbuotojas turėtų daugiausia vieną viršininką. Ji tai padarys nutraukdama kai kuriuos senus ir pradėdama naujus projektus. Aukščiau pateiktą pavyzdį būtų galima pertvarkyti panaikinus projektą 3-4 ir sukūrus naują projektą 3-5, tačiau tai – ne vienintelis būdas.

Užduotis

Raskite būdą „Ūbr“ persitvarkyti taip, kad joks programuotojas neturėtų dviejų arba daugiau viršininkų. Taip pat, po pertvarkos „Ūbr“ nori vykdyti kaip įmanoma daugiau projektų.

Jei yra daugiau nei vienas būdas tai padaryti, raskite tokį, kuris panaikintų kuo mažiau prieš pertvarką vykdytų projektų.

Jei vis dar yra keli galimi būdai, pateikite bet kurį iš jų.

Pradiniai duomenys

Pirmoje eilutėje pateikiami du skaičiai – programuotojų skaičius N ir prieš pertvarką vykdytų projektų skaičius M. Kitos M eilučių aprašo tuos projektus: kiekvienoje iš jų pateikiama po du skirtingus sveikuosius skaičius tarp 1 ir N, nurodančius, kurie du programuotojai yra atsakingi už atitinkamą projektą.

Rezultatai

Pirmoje eilutėje išveskite tris skaičius K, P, S (privalo galioti K=M-P+S):

  • K - skaičius projektų, kuriuos bendrovė vykdys po pertvarkos;
  • P - skaičius projektų projektų, kurie bus nutraukti;
  • S - skaičius projektų, kurie bus pradėti.

Tolesnėse P eilučių išveskite po du skaičius, apibūdinančius projektus, kurie bus nutraukti. Tolesnėse S eilučių išveskite po du skaičius, apibūdinančius projektus, kurie bus pradėti.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
6 5
1 2
1 3
4 2
4 3
5 6
 
5 1 1
4 3
1 5
 
Sąlygoje pateiktas pavyzdys.
 
3 0
 
2 0 2
1 2
1 3
 
Pradėjus šiuos projektus pirmas programuotojas neturės viršininkų, o antras ir trečias - turės po vieną. Daugiau projektų pradėti neįmanoma.

Ribojimai

1\\leqN\\leq1000000

0\\leqM\\leq1000000