Fiindcă nu m-am calificat la ONI, am vacanţă de primăvară. Am luat harta rutieră a ţării şi am marcat n oraşe pe care le consider interesante şi merită vizitate. Am numerotat cele n oraşe de la 1 la n. Oraşul în care locuiesc este numerotat cu x.
Vacanţa nu este lungă, aşa că am hotărât că aş putea vizita exact k oraşe situate pe un traseu care respectă simultan următoarele condiţii (numim un astfel de traseu valid):
1. Traseul porneşte din oraşul în care locuiesc (oraşul x).
2. Între oricare două oraşe consecutive de pe traseu trebuie să existe un drum direct (drum care nu trece prin alte oraşe).
3. Traseul trece prin exact k oraşe distincte.
4. Pentru orice oraş y de pe traseu, distanţa (numărul de drumuri directe parcurse) pe traseul respectiv de la oraşul x la oraşul y (exprimată în număr de drumuri directe parcurse pe traseu) este minimă (adică nu există un alt traseu pe hartă de la x la y având lungime strict mai mică).
Două trasee valide sunt considerate disjuncte dacă ele nu conţin un acelaşi drum direct.
Cerinţă
Cum eu nu m-am calificat la ONI, scrieţi un program care să mă ajute să determin numărul maxim de trasee valide disjuncte.
Date de intrare
Fişierul de intrare trasee.in conţine pe prima linie patru numere naturale n, m, x, k separate prin câte un spaţiu, care reprezintă numărul de oraşe, numărul de drumuri directe dintre oraşe, numărul oraşului în care locuiesc şi respectiv numărul de oraşe aflate pe un traseu. Următoarele m linii conţin cele m drumuri directe de pe hartă, câte un drum pe o linie. Fiecare drum direct este specificat prin două numere naturale distincte cuprinse între 1 şi n, separate printr-un spaţiu, reprezentând oraşele conectate de drumul respectiv.
Date de ieşire
Fişierul de ieşire trasee.out va conţine o singură linie pe care va fi scris numărul maxim de trasee valide disjuncte.
Restricţii
1 ≤ n ≤ 200
1 ≤ x ≤ n
1 ≤ k ≤ n
Între două oraşe poate exista cel mult un drum direct. Drumurile sunt bidirecţionale.
Exemple
trasee.in
trasee.out
Explicaţii
7 8 1 3
1 3
2 3
5 3
4 6
4 7
1 4
6 1
6 7
3
Oraşul de plecare este oraşul 1. Există patru trasee valide care trec prin exact 3 oraşe, plecând din 1 (1-3-2, 1-3-5, 1-4-7, 1-6-7). Numărul maxim de trasee valide disjuncte este 3. O soluţie ar putea fi 1-3-2, 1-4-7, 1-6-7.
