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