Šeštadieninė informatikos olimpiadininkų mokykla

Šiąnakt visi kariūnai dalyvauja papildomose pratybose dykumoje, nes... praleido daugiau kaip pusę orientavimosi dykumoje paskaitų . Tad nenuostabu, kad nei vienas iš vadų nenutuokia į kurią pusę reikėtų žygiuoti. Užtat „pažangieji“ kariūnai, daugybę naktų praleidę naktiniuose budėjimuose, puikiai orientuojasi pagal žvaigždes. Nepasitikėdami savo žiniomis, vadai liepė visiems kariūnams įvardinti, kokias žvaigždes jie mato danguje, t.y., įvardinti tas matomas žvaigždes, kurias kariūnai tikrai atpažįsta. Norėdami parodyti savo žinias kariūnai vardino kuo daugiau pažįstamų žvaigždžių nekreipdami dėmesio į tai, kad kai kurie jų kolegos galbūt jau parodė tas pačias žvaigždes ir rodydami pavadino jas tais pačiais ar visiškai kitais vardais. Vadai sunumeravo visas žvaigždes bei visus pasiūlytus pavadinimus ir susižymėjo visas pasiūlytas poras. Pasirodė, kad skirtingų vardų buvo paminėta lygiai tiek, kiek ir žvaigždžių.

Vadai nori sudaryti žvaigždžių ir pavadinimų porų rinkinį, kuriame kiekvienai žvaigždei būtų priskirtas vienas iš paminėtų pavadinimų. Rinkinyje skirtingos žvaigždės turi gauti skirtingus pavadinimus; žvaigždė gali gauti ir tokį pavadinimą, kuris jai nebuvo pasiūlytas.

Kiekvienas rinkinys įvertinamas kariūnų balsais: rinkinys gauna tiek kariūnų balsų, kiek kartų kariūnų apklausoje buvo paminėtos rinkinyje esančios poros. Vadai nori rasti tokį rinkinį, kuris gautų daugiausia balsų. Jeigu egzistuoja keli tokie rinkiniai, tuomet pasirenkamas bet kuris iš jų.

Parašykite programą, kuri iš kariūnų apklausos rezultatų surastų daugiausiai kariūnų balsų gavusį žvaigždžių numerių ir jiems priskirtų pavadinimų rinkinį.

Pradiniai duomenys

Pirmoje eilutėje įrašyti du tarpais atskirti sveikieji skaičiai: N () – žvaigždžių skaičius bei P () – kariūnų spėjimų skaičius. Likusiose P eilučių įrašyta po du tarpais atskirtus sveikuosius skaičius – žvaigždės, kurios pavadinimą bando atspėti kariūnas, numeris ir apklausos metu šiai žvaigždei priskirto pavadinimo numeris.

Rezultatai

Turi būti lygiai N eilučių. Kiekvienoje eilutėje turi būti įrašyta po vieną sveikąjį skaičių – i-ojoje eilutėje turi būti įrašytas i-ąjį numerį turinčiai žvaigždei priskirto pavadinimo numeris.

Pavyzdys

3 8
1 2
2 1
3 2
1 3
2 2
3 1
1 2
3 2

3
1
2