Nemzetközi Informatikai Diákolimpia 1993

Megnyerted a kanadai légitársaság versenyét. A díj egy kanadai körutazásra szóló szabadjegy. Az utazás a légitársaság listáján szereplő legnyugatibb  városban kezdődik. Első részében csak nyugat-keleti irányban repülhetsz, és el kell jutnod a légitársaság listáján szereplő legkeletibb városba. Az utazás második részében csak kelet-nyugati irányban repülhetsz, és vissza kell jutnod az indulási helyre. Egyetlen városba sem repülhetsz kétszer, az indulási helyet kivéve, amelyet pontosan kétszer kell felkeresned (az utazás kezdetén, illetve végén). Természetesen nem repülhetsz más légitársaság gépével, és más közlekedési eszközt sem használhatsz.

A következő feladatot kell megoldanod: Adott városok egy listája, továbbá azoknak a várospároknak egy listája, amelyek között közvetlen légijárat van. Meg kell keresni azt az útvonalat, amely a lehető legtöbb várost érinti a fenti feltételek betartásával.

Bemenet:

Az ITIN.DAT ASCII állományban különböző adatsorozatok vannak. Ezeket egy-egy üres sor választja el egymástól (vagyis egy olyan sor, amelyben csak "sor vége" karakter van). Az utolsó adatsorozat után nincs üres sor.

Egy-egy adatsorozat felépítése a következő:

• Első sor: a légitársaság listáján szereplő városok száma (N), a légitársaság közvetlen repülőjáratainak száma (V). N 100-nál nem nagyobb, V tetszőleges pozitív egész szám.
• A következő N darab sor mindegyikében a légitársaság listáján szereplő egy-egy város neve van. A városok neve nyugat-keleti irányban van felsorolva. Vagyis az i-edik város akkor és csak akkor van keletre a j-edik várostól,  ha i>j. (Ugyanazon hosszúsági fokon nem lehet egynél több város.) A városnevek legfeljebb 15 betűből és / vagy számjegyből álló karaktersorozatok, pl. AGR34 vagy BEL4.
• A következő V darab sor mindegyikében két-két városnév van, egymástól egyetlen szóközzel elválasztva. A városnevek biztosan az előző listából valók. A város1 város2 pár megadása azt jelenti, hogy van közvetlen repülőjárat város1-ből város2-be, valamint fordítva is, város2-ből város1-be.

Kimnenet:

Az egyes adatsorozatokra adott megoldásokat az ITIN.SOL ASCII állományba kell írni. Az adatsorozatokat egy-egy üres sor választja el egymástól. Ha egy adatsorozatra van a feltételeket kielégítő megoldás, akkor ki kell írni:

• Az első sorba a városok számát, N-et, amely a bemenő adatok között szerepelt.
• A következő sorba az utazás során felkeresett, különböző városnevek számát. (M)
• A következő M+1 sorba soronként egy-egy városnevet, mégpedig abban a sorrendben, ahogyan a városokat az utazás során végigjárod. Az első és az utolsó városnévnek ugyanannak kell lennie.

Ha egy adatsorozatra nincs a feltételeket kielégítő megoldás, akkor csak két sort kell írni az ITIN.SOL állományba:

• Az első sorba a városok számát, N-et, amely a bemenő adatok között szerepelt.
• A második sorba a "NO SOLUTION" szöveget.

Példa:
 

ITIN.DAT	ITIN.SOL
8 9 Vancouver Yellowknife Edmonton Calgary Winnipeg Toronto Montreal Halifax Vancouver Edmonton Vancouver Calgary Calgary Winnipeg Winnipeg Toronto Toronto Halifax Montreal Halifax Edmonton Montreal Edmonton Yellowknife Edmonton Calgary	8 7 Vancouver Edmonton Montreal Halifax Toronto Winnipeg Calgary Vancouver
5 5 C1 C2 C3 C4 C5 C5 C4 C2 C3 C3 C1 C4 C1 C5 C2	5 NO SOLUTION