Državno natjecanje iz informatike 2019. / Prva podskupina (1. i 2. razred) - 3. zadatak

Antonio organizira šahovski turnir.

Na turniru će sudjelovati ukupno N ekipa, svaka od kojih se sastoji od neparnog broja članova K.

Za svakog igrača na turniru poznata je njegova snaga predstavljena prirodnim brojem pri čemu veći broj označava veću snagu, tj. jačeg igrača.

Dva igrača na turniru ne smiju imati istu snagu.

Ukupno će se održati M mečeva, od kojih u svakom sudjeluju dvije ekipe.

Meč se sastoji od K partija: najjači igrač iz prve ekipe igra protiv najjačeg igrača iz druge ekipe, drugi najjači igrač iz prve ekipe igra protiv drugog najjačeg igrača iz druge ekipe, itd.

U susretu dvaju igrača pobjeđuje onaj s većom snagom.

Od ukupno K odigranih partija, ekipa koja je ostvarila više pobjeda smatra se pobjednikom meča.

Antonio je zamislio ishod jednog mogućeg turnira.

Točnije, odredio je broj ekipa N, te M uređenih parova (A, B) koji označavaju da se održao meč između ekipa A i B, te je ekipa A pobijedila.

No, Antonio nije uspio pridružiti snage igračima na način da dani susreti dobiju tražene ishode.

Zato traži vašu pomoć: odredite neparan broj igrača K manji od 200, te N · K jedinstvenih prirodnih brojeva između 1 i 109 koji predstavljaju snage igrača na turniru.

Između svakog para ekipa održat će se najviše jedan meč. Garantirano je da, uz dane uvjete, uvijek postoji rješenje koje zadovoljava tražena ograničenja.

Ulazni podaci

U prvom su retku prirodni brojevi N (1 ≤ N ≤ 100), broj ekipa, i M (1 ≤ M ≤ N(N-1)/2), broj mečeva.

U sljedećih su M redaka po dva različita prirodna broja Ai i Bi (1 ≤ Ai, Bi ≤ N) sa značenjem da ekipa Ai pobjeđuje ekipu Bi.

Parovi se ne ponavljaju, tj. između dviju ekipa igra se najviše jedan meč.

Izalzni podaci

U prvi redak ispišite K, broj igrača u svakoj ekipi.

K mora biti neparan prirodan broj manji od 200.

U idućih N redaka ispišite po K prirodnih brojeva između 1 i 109 , odvojenih razmakom, koje označavaju snage igrača u timu koji opisuje taj redak.

Timovi moraju biti ispisani redom od tima 1 do tima N, dok igrači unutar pojedinog tima mogu biti dani u bilo kojem poretku.

Svih N · K brojeva moraju biti međusobno različiti.

Primjer zadatka

Ulaz

3 3
1 2
2 3
3 1

Izlaz

3
30 20 10
25 16 15
24 22 12

Ulaz

3 3
3 2
3 1
2 1

Izalz

3
7 4 1
8 5 2
9 6 3