Programozás‎ > ‎Feladatok‎ > ‎

Ádám-Éva (OKTV)

Ádám és Éva különböző városokban lakik és találkozni szeretnének egymással. Vannak olyan városok, ahova Ádám nem léphet be, illetve olyanok, amelyek Éva számára tiltottak. Bármely két város közötti közvetlen út megtétele ugyanannyi időbe kerül. 

Feladat

Készíts programot, amely megadja, hogy mely város lesz az, amelyben a leghamarabb találkozhatnak!

Bemenet

A standard bemenet első sorában a városok száma (1≤N≤1000), a közöttük levő közvetlen utak száma (1 ≤ M ≤ 100 000), valamint Ádám és Éva városának sorszáma (1 ≤ A, E ≤ N) van. A következő M sor soronként egy-egy közvetlen út két végpontjának sorszámát 
(1 ≤ Ui ≠ Vi ≤ N) tartalmazza. Az utolsó előtti sorban Ádám tiltott városai száma (0 ≤ TA < N), majd a TA darab tiltott város sorszáma
(1 ≤ TVAi  ≤ N) van egy-egy szóközzel elválasztva. Az utolsó sor
ban Éva tiltott városai száma (0 ≤ TE < N), majd a TE darab tiltott város sorszáma (1 ≤ TVEi ≤ N) található egy-egy szóközzel elválasztva.

Kimenet

A standard kimenet első sorába annak a városnak a sorszámát kell írni, ahol leghamarabb találkozhatnak! Ha több ilyen város van, akkor a legkisebb sorszámút kell kiírni! Ha nincs ilyen város, akkor 0-t kell kiírni!

Példa

Bemenet  Kimenet
5 6 1 4
1 2
1 3
5 3
5 2
2 4
4 5
2 5 2
1 2
3



Tesztadatok

Címkék

A feladat forrása: OKTV 2015-2016, 2. forduló
Algoritmusok: 

megoldás