NézetNyomtat

Vidámpark (Megoldás)
Címkék > Feladat
Versenyek > Nemes Tihamér OKSzTV > 2007 > Döntő > 11-13. osztály

Vidámpark

Egy vidámpark $N$ részlegből áll, a részlegeket az $1,\ldots,N$ számokkal azonosítják, az 1. részleg a bejárat, az N. részleg a kijárat. Minden részlegbe ugyanazzal az egységes jeggyel le­het bemenni. A részlegeket egyirányú utak kötik össze. Ha egy részlegben elhasználunk egy jegyet, akkor el kell hagyni azt a részleget, tehát át kell menni egy másik részlegbe. Ha K da­rab jegyünk van, és mindet el akarjuk használni, akkor meg kell határoznunk egy olyan $R_1=1, \ldots, R_k=N$ sétát, amely a részlegeknek egy olyan felsorolása, amely a bejárattal kezdődik, a ki­járattal végződik, és minden $i$-re ($1\le i < K$) az $R_i$ részlegből közvetlenül át lehet menni az $R_{i+1}$ részlegbe. (Ugyanazon részleg természetesen többször is előfordulhat a sétában.)

Feladat

Készíts programot (VIDAM.PAS, VIDAM.C, …), amely meghatároz egy olyan pontosan $K$ részleget tartalmazó sétát, amely a bejárattal kezdődik, a kijárattal végződik!

Bemenet

A VIDAM.BE szöveges állomány első sora három egész számot tartalmaz egy-egy szó­közzel elválasztva. Az első a részlegek száma ($2\le N \le 100$), a második a részlegeket összekötő közvetlen utak száma ($1 \le M\le 5000$), a harmadik pedig a jegyek száma ($2\le K \le 200$). A további $M$ sor mindegyike két egész számot tartalmaz egy szóközzel elválasztva ($1\le U,V\le N, U\ne V$), ami azt jelenti, hogy az $U$ részlegből van közvetlen út a $V$ részlegbe.

Kimenet

A VIDAM.KI szöveges állomány egyetlen sort tartalmazzon! A sor az egyetlen 0 számot tartalmazza, ha nincs megoldás! Egyébként pontosan $K$ egész számot egy-egy szóközzel elvá­lasztva, ami egy $K$ hosszúságú séta a bejárattól a kijáratig!

Példa

VIDAM.BEVIDAM.KI
6 10 7
1 2
2 1
2 6
1 5
1 3
3 5
5 4
5 6
4 3
6 4
1 5 6 4 3 5 6

Teszadatok