Rezolvare PBinfo #4064

Cerința

Într-un oraș sunt n case numerotate de la 1 la n. Între anumite case sunt străzi bidirecționale. În casa cu numărul g locuiește Ghiocel. El are k colege ale căror numere de casă îi sunt cunoscute și Ghiocel dorește să le ducă ghiocei la inceputul lunii martie. Pentru că este leneș, Ghiocel se decide să ducă ghiocei colegei sau colegelor care stă (stau) la o casă până la care Ghiocel are de parcurs un număr minim de străzi. Ajutați-l pe Ghiocel să determine numerele acestor case.

Date de intrare

Fișierul de intrare ghiocel.in conține pe prima linie numerele n m g, reprezentând numărul de case, numărul de străzi și numărul casei în care locuiește Ghiocel. Urmează m linii cu câte două numere i j, cu semnificația: casele i și j sunt legate printr-o stradă bidirecțională. Pe următoarea linie se află numărul k a colegelor lui Ghiocel, iar pe ultima linie se află k numere distincte cuprinse între 1 și n, reprezentând numerele caselor unde locuiesc colegele lui Ghiocel.

Date de ieșire

Fișierul de ieșire ghiocel.out va conține pe prima linie numerele caselor unde locuiesc colege de-ale lui Ghicel până la care acesta are de parcurs un număr minim de străzi. Numerele se vor afișa în ordine crescătoare și separate prin câte un spațiu.

Restricții și precizări

• 1 ≤ n ≤ 100
• 1 ≤ m ≤ n * (n - 1) / 2
• 1 ≤ i, j ≤ n
• 1 ≤ k ≤ n

Exemplu:

ghiocel.in

10 12 6
1 2
1 7
1 10
2 4
2 5
2 6
3 4
4 5
5 6
7 8
8 10
9 10
4
1 4 8 10

ghiocel.out

1 4

Explicație

Ghiocel locuiește în casa cu numărul 6. Colegele lui stau în casele 1 4 8 10. Până la casele 1 și 4 ajunge mergând pe un număr minim de străzi.