Skup logičkih formula se sastoji od određenog broja iskaznih slova, i određenog broja implikacija (između tih iskaznih slova). Za implikacije smatramo da su unapred dokazane, dok elementarni iskazi moraju biti dokazani ili direktno ili primenom pravila modus ponens, kojim se iz ranije dokazanog izkaza \(A\), na osnovu implikacije \(A \Rightarrow B\) dokazuje iskaz \(B\).
\[\frac{A\qquad A \Rightarrow B}{B}\]
Potrebno je odrediti najmanji mogući broj iskaza koje je potrebno dokazati direktno, tako da se zatim iz njih i datih implikacija mogu primenom pravila modus ponens dokazati svi ostali iskazi.
Sa standardnog ulaza se unosi broj elementarnih iskaza \(m\) (\(1 \leq m \leq 10^4\)), a zatim broj implikacija \(n (1 \leq n \leq 10^4)\). Nakon toga se unosi niz parova brojeva \(i\) i \(j\) (\(0 \leq i < m\)), koji predstavljaju implikacije \(p_i \Rightarrow p_j\).
Na stanadardni izlaz ispisati najmanji broj iskaza koje treba dokazati.
6 7 0 1 1 3 1 2 3 0 2 4 4 2 5 2
2
Dovoljno je, na primer, dokazati formule 0 i 5. Nije dovoljno dokazati samo jednu formulu.