NézetNyomtat

Hajók (Megoldás)
Címkék > Feladat

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.inmexico.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