Fiolki [B]

Limit pamięci: 128 MB

Bajtazar jest chemikiem. Przeprowadza eksperyment, którego celem jest uzyskanie specyfiku X - mikstury rozwiązującej wszelkie problemy ludzkości.

Bajtazar posiada fiolek ponumerowanych liczbami od do , w których znajdują się różne płynne substancje. Fiolka o numerze zawiera całkowitą liczbę gramów substancji . Aby uzyskać specyfik X, należy wykonać sekwencję kroków. Każdy krok polega na przelaniu całej zawartości pewnej fiolki do innej (możemy przy tym założyć, że fiolki mają odpowiednio dużą pojemność, a także, że przy przelewaniu nie uronimy ani kropli). Fiolka, z której przelano substancję, jest odstawiana na półkę i nie jest wykorzystywana w dalszej części eksperymentu.

O pewnych parach substancji wiadomo, że reagują ze sobą, tworząc związek chemiczny, który wytrąca się w postaci osadu. Dla każdej takiej reakcji, na jeden gram pierwszej substancji przypada jeden gram drugiej, a w jej wyniku powstają dwa gramy osadu. Reakcja trwa, dopóki któryś z jej substratów się nie skończy. Wytrącony osad nie reaguje z żadną substancją i do końca eksperymentu przylega do ścianki fiolki, w której powstał. Pewne reakcje dokonują się szybciej niż inne - jeśli wiele substancji znajdzie się naraz w jednym roztworze, reakcje pomiędzy parami substancji wykonują się w ustalonej, znanej Bajtazarowi kolejności. Po każdym kroku Bajtazar czeka, aż substancje w docelowej fiolce przereagują, i dopiero wtedy wykonuje kolejny krok.

Bajtazar zastanawia się, czy sekwencja kroków prowadząca do uzyskania specyfiku X jest optymalna. Chciałby wiedzieć, jaka część substratów marnuje się w wyniku wykonania wszystkich kroków. Poprosił Cię zatem o pomoc w znalezieniu łącznej liczby gramów wytrąconego osadu.

Wejście

Pierwszy wiersz wejścia zawiera trzy liczby całkowite , oraz (, ), oznaczające kolejno: liczbę fiolek (a więc także liczbę różnych substancji), długość sekwencji kroków eksperymentu oraz liczbę par substancji, której ze sobą reagują, wytrącając osad.

W drugim wierszu znajduje się ciąg liczb całkowitych (), określających początkową liczbę gramów substancji w fiolce numer .

W kolejnych wierszach znajduje się opis sekwencji kroków prowadzących do uzyskania specyfiku X: -ty z tych wierszy zawiera dwie liczby całkowite (), oznaczające, że -ty krok polega na przelaniu zawartości fiolki numer do fiolki numer . Można założyć, że jeśli w pewnym kroku wylewamy zawartość fiolki, to ta fiolka nie zostanie użyta w żadnym z kolejnych kroków.

W następnych wierszach znajduje się opis par substancji, które reagują ze sobą, tworząc osad: -ty z tych wierszy zawiera dwie liczby całkowite , () oznaczające, że jeśli substancje i znajdą się jednocześnie w jednej fiolce, to zajdzie między nimi reakcja i wytrąci się osad. Pary substancji podane są w kolejności zgodnej z priorytetem wykonywania reakcji, tzn. w przypadku, gdy w fiolce znajdą się się co najmniej dwie pary reagujących ze sobą substancji, w pierwszej kolejności rozpocznie się (i całkowicie zakończy) reakcja pary substancji podanej na wejściu najwcześniej. Żadna nieuporządkowana para liczb nie powtórzy się wśród tych wierszy.

Wyjście

W jedynym wierszu wyjścia powinna się znaleźć jedna liczba całkowita, oznaczająca łączną liczbę gramów wytrąconego osadu po wykonaniu całej sekwencji kroków eksperymentu.

Przykład

Dla danych wejściowych:

3 2 1
2 3 4
1 2
3 2
2 3

poprawną odpowiedzią jest:

6

Autor zadania: Jakub Radoszewski.