Prihlásenie Registrácia  

B - Reakcie

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Ak by sme chceli veľmi zovšeobecňovať, tak ľudia z Ústavu chemických vied (ÚCHV) sa venujú objavovaniu nových chemických zlúčenín v prírode a objavovaniu postupov na vyrobenie nových alebo už známych chemických zlúčenín z iných už existujúcich zlúčenín. Chemické zlúčeniny sa zvyčajne vytvárajú pomocou chemických reakcií. Wikipédia hovorí: Chemická reakcia je premena reaktantov na produkty. Je to dej, pri ktorom spolu reaguje jedna alebo viaceré látky za vzniku jedného alebo viacerých produktov (látok).

Na ÚCHV majú (ako už možno viete) sklad chemických látok. Navyše tam sú aj laboratória, v ktorých vedia robiť rôzne chemické reakcie (samozrejme nie všetky, iba tie, na ktoré majú podmienky). Ako to už býva, v chemickom sklade materiálu veľa nemajú. A tak, keď v laborátóriu potrebujú spraviť pokus s nejakou chemickou látkou, ktorú práve na sklade nemajú, musia začať chemici hútať, či si ju náhodou nevedia vyrobiť z toho, čo ešte na sklade majú. Riaditeľa ÚCHV by preto zaujímalo, s koľkými rôznymi chemickými látkami môžu laboranti ÚCHV pracovať.

Úloha

Na svete je známych N rôznych chemických látok a zlúčenín. Kvôli jednoduchosti ich bude označovať číslami od 0 po N-1. Na sklade ÚCHV je presne S z nich. Na ÚCHV vedia vo svojich laboratóriach zrealizovať R druhov chemických reakcií. O každej z nich vieme, aké reaktanty sú potrebné, a čo sú jej produkty. Vytvorte program, ktorý načíta údaje o chemických látkach na sklade ÚCHV a reakciách, ktoré na ÚCHV vedia zrealizovať. Výstupom programu nech je počet chemických látok, ktoré má ÚCHV k dispozícii, t.j., alebo ich má na sklade alebo ich vedia z látok na sklade vyrobiť.

Vstup

Prvý riadok vstupu obsahuje medzerami oddelené čísla N (1 ≤ N ≤ 2000), S (1 ≤ SN) a R (1 ≤ R ≤ 200). Druhý riadok vstupu obsahuje S medzerami oddelených čísel predstavujúcich chemické látky, ktoré sa nachádzajú na sklade ÚCHV. Ďalej nasleduje R riadkov popisujúcich realizovateľné chemické reakcie. Každý riadok popisuje jednu chemickú reakciu a skladá z nasledovných medzerami oddelených čísel:

  • počet reaktantov reakcie PR(1 ≤ PR ≤ 5),
  • počet produktov reakcie PP(1 ≤ PP ≤ 5),
  • PR čísel predstavujúcich číselné označenia látok, ktoré sú reaktantami v reakcii,
  • PP čísel predstavujúcich číselné označenia látok, ktoré sú produktmi reakcie.

Výstup

Vypíšte číslo (ukončené znakom konca riadka) vyjadrujúce počet chemických látok, ktorými disponuje ÚCHV, t.j., alebo sú na sklade, alebo ich vedia vyrobiť z látok na sklade.

Príklad

Vstup:

10 4 2
0 5 2 1  
3 2 3 2 5 9 0
2 2 0 2 3 8

Výstup:

7

Pomocou druhej reakcie vedia vyrobiť látky 3 a 8. To im potom dovolí použiť prvú reakciu a vyrobiť novú látku 9.