bile

Avem N bile (numerotate de la 1 la N), oricare doua bile avand greutati diferite. Pentru a descoperi bila cu greutatea mediana (deci cea de a (N+1)/2-a bila, in ordinea greutatilor) putem utiliza o balanta cu doua platane. Putem plasa cate o bila pe fiecare platan si astfel putem afla care dintre cele doua bile este mai grea. Ca urmare a rezultatelor obtinute in urma unui set de astfel de cantariri, putem elimina unele dintre bile, despre care putem afirma cu siguranta ca nu au greutatea mediana.
De exemplu sa consideram N=5 bile, intre care s-au efectuat M=4 cantariri, obtinand urmatoarele rezultate:
Bila 2 este mai grea decat bila 1.
Bila 4 este mai grea decat bila 3.
Bila 5 este mai grea decat bila 1.
Bila 4 este mai grea decat bila 2.
Din rezultatele de mai sus, desi nu putem determina exact bila cu greutatea mediana, putem afirma ca bila 1 si bila 4 nu pot avea greutatea mediana, deoarece bilele 2, 4, 5 sunt mai grele decat bila 1, iar bilele 1, 2, 3 sunt mai usoare decat bila 4. Prin urmare putem elimina aceste doua bile.

Cerinta
Scrieti un program care sa determine pe baza unui set de cantariri dat numarul de bile care nu pot avea greutatea mediana.

Date de intrare

Fisierul de intrare bile.in contine pe prima linie numarul natural N reprezentand numarul de bile si numarul natural M reprezentand numarul de cantariri, separate printr-un spatiu. Fiecare dintre urmatoarele M linii contine doua numere naturale cuprinse intre 1 si N cu semnificatia "bila corespunzatoare primului numar este mai grea decat bila corespunzatoare celui de al doilea numar".

Date de iesire

Fisierul de iesire bile.out contine o singura linie pe care se afla numarul de bile care nu pot avea greutatea mediana.

Restrictii

N numar natural impar, 0<N<=300
M<=5000
Este posibil ca in fisierul de intrare sa existe mai multe cantariri pentru aceeasi pereche de bile; evident la fiecare cantarire obtineti acelasi rezultat.

Exemple

Timp maxim de executie/test: 0.1 secunde

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:ema at mail.dntis.ro