Programozás‎ > ‎Feladatok‎ > ‎

Ádám-Éva (NT)

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

Feladat

Készíts programot, amely megadja, hogy mely városban találkozzanak, hogy ketten együtt összesen minimális számú lépést tegyenek meg!

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 városokat az 1,...,N számokkal azonosítjuk. A következő M sor mindegyike két város sorszámát tartalmazza, amelyek között van mindkét irányban járható közvetlen út. (1 ≤ Ui ≠ Vi ≤ N). 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. Az utolsó sorban Éva tiltott városai száma (0 ≤ TE < N), majd a TE darab tiltott város sorszáma (1 ≤ TVEi ≤ N) található.

Kimenet

A standard kimenet első sorába annak a városnak a sorszámát kell írni, ahol minimális számú lépést megtéve 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
1



Tesztadatok

Csatolmányként

Címkék

A feladat forrása: Nemes Tihamér verseny, 2015-2016, 2. forduló
Algoritmusok: 

megoldás