Hajók
Egy tó partján n város található. Bizonyos városok között
kereskedelmi megállapodás született, ezek között a városok között hajóval
szállítják az árut a kereskedők. A hajók két város között egyenes vonalban
haladnak.
A birodalom királya úgy döntött, megszervezi a városok közötti forgalmot, ezért
egy olyan kereskedelmi útvonalat szeretne tervezni, amely minden várost érint
és a következő tulajdonságokkal bír:
- bárhol kezdődhet és végződhet, de minden várost pontosan egyszer érint
- az útvonal szomszédos városai között létezik kereskedelmi megállapodás
- az útvonal két szomszédos megálló között egyenesen halad
- a baleseteket megelőzendő az útvonal nem metszheti önmagát
A városokat 1-től n-ig számozzuk az óramutató járása szerinti irányban.
Feladat
Írj programot, amely eldönti, hogy lehetséges-e a feltételeknek
megfelelő úvonal tervezése. Ha igen, akkor a program írja ki egy megfelelő útvonal
szerinti sorrendben a városok sorszámát.
Bemenet
A mexico.in szöveges állomány első sora a városok nszámát, második sora
pedig a kereskedelmi egyezségek e számát adja meg. $(3\le n\le 1000)$
Utána e sorban a kereskedelmi egyezségekben résztvevő városok sorszáma olvasható.
Kimenet
A mexico.out szöveges állomány első sorába az "IGEN" vagy "NEM" szöveget kell írni. Ha megvalósítható a terv, akkor a következő n sorba az útvonal állomásait
írjuk ki.
Példa
| mexico.in | mexico.out |
|
7 9 1 4 5 1 1 7 5 6 2 3 3 4 2 6 4 6 6 7 |
IGEN 2 3 4 1 7 6 5 |