Nosaukums
Spēļu kauliņa ceļojums (ways)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
50%

Definīcija

Taisnstūrveida rūtiņu laukums sastāv no N rindām un M kolonnām. Spēļu kauliņš vienā gājienā var pārvietoties no vienas kolonnas rūtiņas uz kādu no nākošās kolonnas rūtiņām. Katrai rūtiņai ir zināmi to nākošās kolonnas rūtiņu rindu uz kurām nākošajā gājienā drīkst iet, numuri. Kauliņš spēles laikā nedrīkst atgriezties rūtiņā kur tas jau reiz bijis.

Spēles sākumā kauliņu novieto kādā no pirmās kolonnas rūtiņām. Pēc tam spēles kauliņu saskaņā ar iepriekšaprakstītajiem noteikumiem pārvieto līdz pēdējai kolonnai. Kad kauliņš sasniedzis pēdējo kolonnu, to pārvieto uz kādu no iepriekš neapmeklētām pirmās kolonnas rūtiņām un atsāk kauliņa pārvietošanu.

Spēle beidzas, kad vairs nav iespējams izdarīt gājienu saskaņā ar noteikumiem.

Uzrakstiet programmu, kas ievadītiem laukuma izmēriem un atļauto gājienu tabulai nosaka kādu lielāko skaitu reižu kauliņu spēles laikā var pārvietot no pirmās līdz pēdējai kolonnai!


Ievaddatu raksturojums

Ievaddatu pirmā rinda satur naturālus skaitļus N un M - laukuma rindu un kolonnu skaitu 1<=N<=50, 2<=M<=10.
Tālāk seko M-1 bloks pa N rindām katrā - atļauto gājienu apraksts katrai no laukuma rūtiņām. Katra j-tā bloka i-tā rinda satur atļauto gājienu sarakstu no i-tās rindas j-tās kolonnas rūtiņas. Pirmais skaitlis rindā norāda no šīs rūtiņas atļauto dažādo gājienu skaitu, kam seko nākošās kolonnas rūtiņu rindu numuri augošā secībā bez atkārtošanās.


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada vesels skaitlis, kas norāda meklēto reižu skaitu. Atbilde var būt 0, ja ne no vienas pirmās kolonnas rūtiņas nevar sasniegt pēdējo kolonnu.


Piezīmes

Piemēra testam šie ceļi ir: 

1->3->3 
2->4->4 
4->2->2

 
Uzdevums izmantots Ukrainas XV informātikas olimpiādē 2002.gadā.


Paraugdati

Stdin
4 3
2 1 3
3 1 2 4
0
2 2 3
1 2
1 2
1 3
2 2 4
Stdout
3

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.