[ seymour @ 20.07.2007. 15:26 ] @
| Da li neko ima ideju kako se na optimalan nacin moze resiti problem koji sam naveo dole? U školu plesa uclanjeno je m mladica i n devojaka. Svako od njih ima svoju listu partnera suprotnog pola sa kojima voli da igra. Lista je uredena tako da svako više voli da igra sa onim partnerom koji se nalazi bliže pocetku u njegovoj listi nego sa onim koji se nalazi bliže kraju. Tako svako najviše voli da igra sa prvim iz svoje liste, a najmanje sa poslednjim, dok sa onima koji nisu u listi uopšte nece da igra. Potrebno je podeliti plesace u muško-ženske parove tako da važi sledeci uslov: ako mladic A i devojka V nisu u paru tada je mladic A u paru sa devojkom koja se nalazi ispred V u njegovoj listi ili je devojka V u paru sa mladicem koji se nalazi ispred A u njenoj listi. Ulaz. U prvoj liniji standardnog ulaznog nalaze se brojevi m i n (1 <= m, n <= 1000). U sledecih n linija opisane su liste mladica: na pocetku i+1-ve linije nalazi se broj k iza koga slede k razmakom razdvojenih brojeva koji predstavljaju listu i-og mladica. Potom sledi m linija u kojima su opisane liste devojaka: na pocetku n+i+1-ve linije nalazi se broj k iza koga slede k razmakom razdvojenih brojeva koji predstavljaju listu i-te devojke. Izlaz. U prvu liniju standardnog izlaza upisati koliko je ukupno parova oformljeno, a u narednim linijama nabrojati te parove tako da u svakoj liniji budu upisana dva razmakom razdvojena broja: redni broj mladica pa redni broj devojke koji igraju u paru. Navesti bilo koje rešenje koje zadovoljava traženi uslov. Primer: Ulaz 3 4 2 1 3 2 4 1 4 1 3 4 2 3 2 1 3 2 1 2 2 3 1 2 1 3 Izlaz 2 2 1 3 3 |