Tűzfal

Az adatok titkosítása egy dolog, de nem sokat érünk vele ha a támadók képesek behatolni a rendszereinkbe és esetlegesen letörölni minden létező fájlt. Így elengedhetetlen, hogy helyes tűzfalbeállításokkal korlátozzuk a rendszereink hozzáférhetőségét, illetve, hogy baj esetén azonnal tudjunk reagálni. A feladatunk így nem más, minthogy kibervédelmi szakértőként egy vírus bejutását követően minél jobban megakadályozzuk annak terjedését oly módon, hogy a hálózat egy pontját tűzfallal lezárjuk, így a vírus nem képes arra tovább haladni. A következő ismeretekkel rendelkezünk:

• A hálózat routerekből (csúcsok) áll, melyek öszekapcsolódhatnak egymással (élek). A csúcsokat pozitív egész számokkal jelöljük és a jelölés egyedi.
• A vírus a hálózat bármely pontján megjelenhet, de mindig szigorúan egyetlen routeren lép be. A belépési pont ismert.
• A vírus képes a routerek közötti kábeleken terjedni, így bármelyik olyan routert elérheti mely közetlenül össze van kötve egy már megfertőzött routerrel.
• A vírus nem képes átterjedni arra a routerre melyre tűzfalat telepítettünk.
• Az támadás egyetlen pillanat alatt zajlik le, így csupán egyetlen routerre van időnk tűzfalat telepíteni.
• A belépési pont már "elveszett", így arra nem telepíthetünk tűzfalat.

A feladat az, hogy egy megadott hálózati infrastruktúra és belépési pont ismeretében megmondjuk azt az egyetlen routert melyre tűzfalat kell telepítenünk ahhoz, hogy a vírus a lehető legkevesebb routert tudja megfertőzni. Ha több ilyen router is a rendelkezésünkre áll, úgy a legkisebb számú kerüljön kiírásra.

Input

A bemenet négy egységből áll:

• Az első sor egy pozitív egész n és a routerek számát adja meg.
• A második sor a vírus belépési e pontját adja meg.
• A harmadik sor a routerek közötti élek m számát adja meg.
• A következőő m darab sor mindegyike egy szóközzel elválasztott számpár, mely az éleket írja le (például 2 5 azt jelenti, hogy a 2-es és 5-ös router össze van kötve).

Output

A kimenet egyetlen egész szám, mely a fentiek ismeretében megmondja, hogy melyik routerre telepítsünk tűzfalat ahhoz, hogy a vírus terjedését követően a lehető legkevesebb router fertőződjön meg. A tűzfallal ellátott router is "tisztának" számít, így legalább 1 routert mindig meg tudunk védeni. Ha több lehetőség közül választhatunk akkor a legkisebbet írjuk ki.

Megkötések

Példa

Magyarázat

2. 0-1-2-3
3.  \
4.   [4]-ok(5)-ok(6)-ok(7)

letöltés szöveges állományként