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 atac2.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 dintre 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 atac2.out conţine un singur număr natural reprezentând timpul total minim cerut.
Restricţii
• 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
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)