atac

Costel, mare pasionat de jocuri de strategie, a descoperit de curând un joc nou. Acesta se joacă pe o hartă compusă din n oraşe, numerotate de la 1 la n, unele dintre acestea fiind conectate prin drumuri directe. Este posibilă deplasarea între oricare două oraşe utilizând drumurile existente. Costel a ajuns înaintea bătăliei finale, când adversarul său mai stăpâneşte un singur oraş. Notăm acest oraş cu x. Costel dispune de u unităţi de armată, fiecare fiind cantonată într-un oraş oarecare, diferit de oraşul x. Pentru a câştiga, Costel trebuie să deplaseze câte o unitate de armată în fiecare dintre oraşele învecinate cu oraşul x. Victoria nu este deloc sigură în situaţia în care timpul total necesar transportului unităţilor nu este minim. Datorită tehnologiei avansate, drumul direct dintre oricare două oraşe poate fi parcurs în timp constant egal cu o unitate de timp.

Cerinţă

Scrieţi un program care să determine timpul total minim de deplasare a tuturor unităţilor necesare în oraşele învecinate cu oraşul x.

Date de intrare

Fişierul de intrare atac.in conţine:

• pe prima linie, 4 numere naturale n, m, u, x, separate prin câte un spaţiu, n reprezentând numărul oraşelor, m reprezentând numărul drumurilor directe existente între oraşe, u reprezentând numărul unităţilor de armată de care dispune Costel, x reprezentând oraşul în care se află armata adversarului.
• pe a doua linie, u numere naturale, separate prin câte un spaţiu, reprezentând oraşele în care se află cantonate cele u unităţi de armată.
• fiecare din următoarele m linii conţine câte două numere naturale a şi b, separate printr-un spaţiu, cu semnificaţia că oraşele a şi b sunt legate printr-un drum direct.

Date de ieşire

Fişierul de ieşire atac.out conţine un singur număr natural reprezentând timpul total minim cerut.

Restricţii şi precizări

• 1 < n ≤ 10000
• 1 < m ≤ 100000
• 0 < u ≤ 70
• Numărul oraşelor învecinate cu oraşul x este cel mult egal cu numărul unităţilor de armată
• Pentru 60% din teste u ≤ 8

Exemplu

atac.in

7 11 3 7
6 1 3
1 4
2 5
3 1
3 5
4 5
5 1
6 2
6 3
6 4
7 4
7 5

atac.out

2

Explicații

Oraşul 7 se învecinează cu oraşele 4 şi 5, deci va fi nevoie să deplasăm doar 2 unităţi dintre cele 3 disponibile.
Timpul minim necesar este 2. Există mai multe variante pentru mutarea unităţilor, de exemplu:

• mutăm unitatea din oraşul 6 în oraşul 4 (1 unitate de timp) şi cea din oraşul 3 în oraşul 5 (1 unitate de timp)
• mutăm unitatea din oraşul 1 în oraşul 4 (1 unitate de timp) şi cea din oraşul 3 în oraşul 5 (1 unitate de timp)