Reakcje chemiczne

Limit pamięci: 64 MB

Bajtek od niedawna uczy się chemii i bardzo go ten przedmiot zafascynował. Postanowił nawet stworzyć własne laboratorium. Już skompletował pewien zestaw związków chemicznych oraz narzędzi do przeprowadzania różnych reakcji. Chciałby teraz pomnożyć swoje zasoby i jest ciekaw, ile różnych związków chemicznych, jakich jeszcze nie posiada, jest w stanie wyprodukować przy użyciu tego, co ma do dyspozycji.

Ponieważ jednak matematyka nie jest jego dobrą stroną, Bajtek poprosił Ciebie o napisanie programu, który wyznaczy liczbę tych związków. Dla uproszczenia zakładamy, że każdy spośród już skompletowanych związków chemicznych Bajtek posiada w nieskończonej ilości.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis posiadanych przez Bajtka związków chemicznych oraz reakcji, jakie jest on w stanie przeprowadzić,
• wyznaczy liczbę związków chemicznych, których Bajtek jeszcze nie ma, ale które jest w stanie wyprodukować,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby całkowite , oraz (, , ), pooddzielane pojedynczymi odstępami i oznaczające odpowiednio: liczbę znanych Bajtkowi związków chemicznych, liczbę związków chemicznych posiadanych przez Bajtka oraz liczbę reakcji, jakie jest on w stanie przeprowadzić. W drugim wierszu znajduje się liczb całkowitych (), pooddzielanych pojedynczymi odstępami i oznaczających numery związków chemicznych posiadanych przez Bajtka. Numery te są parami różne.

W każdym z następnych wierszy znajduje się opis jednej reakcji, jaką potrafi wykonać Bajtek. Opis każdej reakcji składa się z opisu jej substratów (związków chemicznych potrzebnych jako składniki do jej przeprowadzenia) oraz następującego po nim opisu produktów. Opis substratów składa się z liczby całkowitej () oznaczającej liczbę substratów tej reakcji, po której następuje numerów związków chemicznych, potrzebnych do przeprowadzenia reakcji. Następnie w tym samym wierszu znajduje się opis produktów. Składa się on z liczby całkowitej (), oznaczającej liczbę produktów reakcji, po której następuje numerów związków chemicznych, jakie otrzymuje się po przeprowadzeniu -tej reakcji. Każdy z numerów związków chemicznych uczestniczących w reakcji (zarówno substratów, jak i produktów) jest liczbą całkowitą z zakresu od do włącznie. Numery substratów dowolnej reakcji są parami różne; podobnie numery produktów też są parami różne. Może się jednak zdarzyć, że jakiś związek jest jednocześnie substratem i produktem reakcji (może on wówczas być jej katalizatorem). Wszystkie liczby występujące w opisie jednej reakcji są pooddzielane pojedynczymi odstępami.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, oznaczającą liczbę związków chemicznych, których Bajtek jeszcze nie posiada, ale potrafi wyprodukować z już posiadanych związków za pomocą odpowiednich reakcji chemicznych.

Przykład

Dla danych wejściowych:

8 2 4
2 1
2 1 2 2 3 4
2 4 1 1 3
2 2 3 3 2 1 5
2 5 6 3 1 8 2

poprawną odpowiedzią jest:

3

Komentarz do przykładu

W powyższym przykładzie Bajtek potrafi przeprowadzić następujące reakcje:

Na początku posiada on związki i , przy użyciu pierwszej reakcji może otrzymać związki oraz , a następnie, przeprowadzając trzecią reakcję, może wyprodukować związek . Natomiast związków , ani nie jest on w stanie otrzymać.

Autor zadania: Marian M. Kędzierski.