Pentru a primi cu surle si tobe mutilarea invatamantului liceal de
informatica in Romania (care duce, va dati seama, la mutilarea inevitabila
a Olimpiadei de Informatica), propunem aceasta problema, in speranta ca se
va gasi cineva care sa subtieze si programa de pe la facultati.

PROBLEMA 19:            Programa subtirica
DEADLINE:               Luni, 24 mai 1999
TIMP DE IMPLEMENTARE:   O ora
DOMENIU:                Grafuri
PUNCTAJ:                40 dexteri

La Facultatea de ... si ... exista doua alternative pentru ca studentii sa
aiba timp sa asimileze cunostintele: (1) Marirea zilei la 30 de ore, si
(2) Subtierea programei scolare. Optand pentru varianta a doua, Liga
Studentilor introduce o platforma program care:

1) Stabileste care sunt materiile necesare pentru a putea studia o noua
materie. De exemplu, pentru a studia cursul "Management" este nevoie de
cursul "Teorie Economica" si de cursul "Marketing", asta pentru a da un
exemplu strans legat de profilul Facultatii de ... si ...

2) Stabileste care sunt materiile cu adevarat utile dintre toate cele
studiate in facultate. De exemplu, cursul de ... (nu dam nume, dar se poate
completa la intamplare cu sanse mari de a da un raspuns corect) nu este
util la absolut nimic.

3) Cere sa se elimine din programa materiile care nu sunt nici folositoare,
nici nu servesc (direct sau indirect) la invatarea unor materii
folositoare. Vezi exemplul.

4) Cere sa se indice care dintre materii nu pot fi predate in nici o
ordine. De exemplu, cursul "Mecanica" se bazeaza din greu pe cursul
"Ecuatii Diferentiale", dar cursul de "Ecuatii Diferentiale" isi preia
exemplele din "Mecanica". Cerc vicios, deci materiile nu pot fi predate in
nici o ordine fara a "baga pe gat" cunostinte nedemonstrate.

Numarul N de materii predate in facultate nu depaseste 100 (slava Domnului,
desi nici departe nu e), iar pentru comoditatea voastra materiile au fost
codificate prin numerele de la 1 la N.

DATE DE INTRARE: Fisierul PROGRAMA.IN contine pe prima linie numarul de
materii N, numarul de legaturi intre materii care exista, M, si numarul de
materii utile din facultate F (0<=F<=N). Pe urmatoarele M linii se gaseste
cate o pereche de numere X si Y, care inseamna ca materia X este necesara
pentru invatarea materiei Y. Pe ultima linie se gasesc F numere,
reprezentand codificarile materiilor utile.

DATE DE IESIRE:
Fisierul PROGRAMA.OUT contine doua linii mari si (probabil) late. Pe prima
se vor tipari in ordine crescatoare numerele materiilor complet inutile
(vezi definitia de la punctul 3). Pe linia a doua se vor tipari tot in
ordine crescatoare materiile care nu pot fi predate datorita dependentelor
ciclice.

EXEMPLU:
PROGRAMA.IN                     PROGRAMA.OUT
8 6 1                           2 4 5 8
1 3                             3 6
5 4
6 7
3 6
7 8
6 3
7

TIMP DE RULARE: 1 secunda/test.
COMPLEXITATE RECOMANDATA: Cred ca O(M+N), dar nu sunt 100% sigur.