Rete di scuole
Un certo numero di scuole è connesso in una rete di computer. Esistono
degli accordi di scambio tra le scuole: ogni scuola mantiene una lista
di altre scuole a cui distribuisce del software (le "scuole riceventi").
Si osservi che se la scuola B è nella lista di distribuzione della
scuola A, non è detto che A sia nella lista di distribuzione della
scuola B.
Devi scrivere un programma che calcoli il numero minimo di scuole che
debbono ricevere una copia di nuove release di software affinchè
esse possano essere distribuite a tutte le scuole secondo gli accordi precedentemente
stabiliti (Subtask A). Quale ulteriore compito si desidera che spedendo
una nuova release ad una scuola arbitraria tale software raggiungerà
tutte le scuole nel network.
Per potere raggiungere questo obiettivo potrebbe essere necessario
estendere le liste di distribuzione a nuovi membri. Si calcoli il numero
minimo di estensioni che debbono essere operate sulle liste di distribuzione
così che spedendo del software ad una scuola qualunque esso raggiunga
tutte le altre scuole nel network (Subtask B). "Estensione" vuol dire l'aggiunta
di un membro alla lista di distribuzione di una scuola.
Input Data
La prima linea del file INPUT.TXT contiene un interor N:
il numero di scuole connesse in rete (2<=N<=100). Le scuole sono
identificate dai primi N interi positivi. Ciascuna delle successive N linee
di testo descrive le liste di distribuzione di ciascuna scuola. La linea
i+1 contiene gli identificativi delle scuole nella lista di distribuzione
della scuola i. Ogni lista ha termne con uno 0. Una lista vuota è
rappresentata da una linea che contiene un solo zero .
Output Data
Il tuo programma deve scrivere due righe nel file OUTPUT.TXT.
La prima riga deve contenere un intero positivo: la soluzione del subtask
A. La seconda linea deve contenere la soluzione del subtask B.
Example Input and Output
La Figura 1 illustra un possibile file di input e output.
INPUT.TXT
5
2 4 3 0
4 5 0
0
0
1 0
OUTPUT.TXT
1
2