Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: stazas.in

Rezultatų failas: stazas.out

Jei norite pateikti savo sprendimą - prisijunkite.

Pilotų stažas

Valentina labai daug skraido. Ji neseniai perskaitė, jog oro kompanija, su kuria ji skrido pastaruosius N kartų, formuoja įgulą laikydamasi taisyklės, kad pirmojo piloto darbo stažas (kiek pilnų metų darbo patirties jis turi) turi būti vieneriais metais didesnis, nei antrojo piloto darbo stažas. Kompanija neatskleidžia pilotų darbo stažo, tačiau Valentinai pasidarė įdomu, koks galėjo būti didžiausias stažo skirtumas tarp visų pilotų, su kuriais ji skrido per pastaruosius N skrydžių. Ji užsirašė visų pilotų, dirbusių tuose skrydžiuose, pavardes, tačiau neprisimena, kuris iš jų buvo pirmasis pilotas, o kuris – antrasis. Valentina daro prielaidą, jog kiekvieno jų stažas yra tarp 1 ir 50 metų, bei laikotarpyje tarp pirmo ir paskutinio iš tų N skrydžių nė vieno jų stažas nepakito.

Padėkite Valentinai apskaičiuoti didžiausią galimą pilotų stažo skirtumą, remiantis jos prielaidomis ir užrašais.

Pradiniai duomenys

Pirmoje eilutėje – skrydžių skaičius N(2\\leqN\\leq1000) bei pilotų skaičius P(2\\leqP\\leq50). Pilotai yra sunumeruoti nuo 1 iki P. i-ojoje iš tolesnių N eilučių yra pateikti i-ojo skrydžio pilotų numeriai.

Rezultatai

Pirmoje eilutėje – didžiausias galimas pilotų stažo skirtumas. Antroje eilutėje – P tarpais atskirtų sveikųjų skaičių, iš kurių i-asis reiškia piloto, kurio numeris i, stažą. Jeigu galimi keli sprendiniai, išveskite bet kurį. Jeigu Valentinos prielaidos arba užrašai yra klaidingi, išveskite vieną skaičių „-1“.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
4 4
2 3
4 2
3 1
1 4
 
2
3 1 2 2
 
3 3
1 2
1 3
2 3
 
-1