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
|
Tesztadatok
