Rezolvare PBinfo #4630

Cerinţa

Se dă un graf neorientat cu n vârfuri și m muchii. Se numește vârf saturat un vârf care are gradul mai mare sau egal cu jumatatea numărului de vărfuri. Dacă numărul de vărfuri este impar, atunci gradul trebuie să fie mai mare strict decăt jumătatea numărului de vârfuri. Să se afișeze vârfurile saturate din graful dat.

Date de intrare

Fişierul de intrare saturate.in conţine pe prima linie numerele n și m, reprezentând numărul de vârfuri ale grafului, respectiv numărul de muchii. Fiecare dintre următoarele m linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j.

Date de ieşire

Fişierul de ieşire saturate.out va conţine pe prima linie vârfurile cu proprietatea cerută, separate prin câte un spațiu. Dacă graful nu conține niciun vârf saturat, atunci se va afișa Nu exista.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• 0 ≤ m ≤ n(n-1)/2
• 1 ≤ i , j ≤ n

Exemplu:

saturate.in

5 6
1 2
2 3
2 4
2 5
4 5
3 5

saturate.out

2 5

Explicație

Vârful 2 are gradul egal cu 4, vârful 3 au gradul egal cu 3 și sunt saturate, iar restul vârfurilor au gradele mai mici sau egale cu 2, deci nu sunt saturate.