Egy terrorista csapat
elhatározza, hogy Velence városában fogja elkövetni következő merényletét. A
város nagyon sok kis szigetből áll, melyek közt kis gyaloghidakat építettek.
Jelenleg a város olyan szerkezetű, hogy gyalogszerrel is el lehet jutni a város
egy tetszőleges pontjából egy másik tetszőleges pontjába. A terroristák olyan
hidat szeretnének felrobbantani, amely két részre vágja a várost, azaz a híd
felrobbantása után lesznek a városnak olyan pontjai, amelyek közt nem vezet
gyalogút. A terroristák elfogtak és megzsarolnak, hogy írj olyan programot,
amely megad egy ilyen hidat.
Bemenet:
Az INPUT TXT első sora a
tesztesetek számát tartalmazza, majd következnek a tesztesetek. Egy teszteset a
következő szerkezetű. A teszteset első sora tartalmazza a hidak számát
(0<E<10000). ), majd E soron
keresztül következnek az említett hidak, melyek egy számpár
formájában vannak megadva, ahol a számpár tagjai
szigetek azonosítói. A szigetek azonosítói legyenek 100-nál kisebb nem negatív
egészszámok.
Kimenet:
Minden tesztesetre adjunk választ, amely kétféle
lehet. Amennyiben létezik olyan híd, amely "kettévágja" a várost, úgy
adjunk meg egy ilyen hidat, a híd két végén lévő sziget azonosítójának a
segítségével, ellenkező esetben írjuk ki "NINCS MEGFELELO HID".
(Nagy Tibor)