Wschód-Zachód

Limit pamięci: 64 MB

Umowy międzynarodowe podpisane przez Wielce Rozległe Państwo nakładają na nie obowiązek tranzytowy - musi ono umożliwić przewiezienie koleją odpadów nuklearnych z elektrowni u wschodniego sąsiada do punktów utylizacji za zachodnią granicą. Względy ekologiczne nakazują taką organizację ruchu, by pociągi z odpadami jak najszybciej opuściły terytorium kraju.

Sieć kolejowa w tym państwie ma bardzo szczególną strukturę. Składa się ona z miast-węzłów kolejowych oraz dwukierunkowych odcinków torów, łączących miasta-węzły. Między każdymi dwoma miastami istnieje możliwość przejazdu. Ponadto istnieje taki odcinek sieci, którego końce nie są miastami granicznymi, oraz każdy przejazd z miasta na granicy wschodniej do miasta na granicy zachodniej prowadzi przez ten odcinek.

Wszystkie pociągi z odpadami przyjeżdżają na granicę wschodnią tego samego dnia przed świtem, przy czym każdy z nich do innego miasta. Ze względu na niebezpieczeństwo wypadku pociągi jeżdżą tylko w dzień i po żadnym odcinku nie może jednocześnie jechać więcej niż jeden pociąg z odpadami, natomiast dowolnie wiele takich pociągów może oczekiwać w mieście-węźle. Dodatkowo przejechanie jednego odcinka zajmuje pociągowi jeden dzień. Ruch musi być tak zorganizowany, by każdy pociąg z odpadami dojechał do innego przejścia na granicy zachodniej.

Ile co najmniej dni pociągi z odpadami muszą spędzić na terytorium Wielce Rozległego Państwa?

Zadanie

Zadanie polega na napisaniu programu, który:

• wczyta ze standardowego wejścia opis sieci kolejowej i przejść granicznych, do których przyjechały pociągi z odpadami,
• wyznaczy minimalną liczbę dni, jakie musi trwać tranzyt,
• wypisze znalezioną liczbę na standardowe wyjście.

Wejście

Pierwsza linia wejścia zawiera trzy pooddzielane pojedyńczymi odstępami liczby naturalne , . Liczba oznacza liczbę miast-węzłów (są one ponumerowane od 1 do ), zaś i oznaczają liczby przejść granicznych odpowiednio na granicy wschodniej i zachodniej. Przejścia na granicy wschodniej oznaczone są liczbami , zaś na zachodniej liczbami .

W kolejnych liniach znajduje się opis odcinków sieci kolejowej. Każda linia opisu zawiera dwie różne liczby naturalne oddzielone pojedynczym odstępem, . Są to numery miast-węzłów połączonych odcinkiem torów.

W -ej linii znajduje się jedna liczba naturalna , , oznaczająca liczbę pociągów z odpadami. W następnej (i ostatniej) linii wejścia znajduje się pooddzielanych pojedyńczymi odstępami różnych liczb naturalnych, z których każda jest nie większa niż . Są to numery przejść granicznych na granicy wschodniej, do których przyjechały pociągi z odpadami.

Wyjście

Pierwsza i jedyna linia wyjścia powinna zawierać dokładnie jedną liczbę całkowitą, równą minimalnej liczbie dni, jakie odpady muszą spędzić na terytorium państwa.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

4

Strzałki przedstawiają ruch pociągów w kolejnych dniach dla jedej z optymalnych organizacji ruchu kolejowego - pętla oznacza, że danego dnia pociąg stał w mieście-węźle.

Autor zadania: Karol Cwalina.