politics
In Parlamentul Romaniei nici un partid nu are majoritate parlamentara, asa ca adoptarea legilor este un proces extrem de dificil.
In Parlament exista n parlamentari, pe care ii vom identifica prin numere de la 1 la n.
Este de dorit formarea unei coalitii din mai multe partide, coalitie care sa fie majoritara (numarul de parlamentari din partidele coalitiei sa fie cel putin egal n/2+1) .
Pentru ca la formarea unei coalitii, negocierile sunt cu atat mai indelungate cu cat numarul de partide implicate este mai mare, este de dorit o coalitie majoritara, formata dintr-un numar minim de partide.
Un partid va fi identificat prin numarul de ordine al presedintelui partidului (acesta este parlamentarul din partidul respectiv cu numarul de ordine cel mai mic).

Cerinta
Sa se scrie un program sa determine o coalitie majoritara, formata dintr-un numar minim de partide.

Date de intrare
Fisierul de intrare politics.in contine pe prima linie doua numere naturale separate prin spatiu n si m, reprezentand numarul total de parlamentari si respectiv numarul de relatii aflate pe urmatoarele m linii ale fisierului de intrare. Pe fiecare dintre urmatoarele m linii se afla cate doua numere naturale x si y, numere cuprinse intre 1 si n, separate printr-un spatiu, cu semnificatia "parlamentarul x si parlamentarul y se afla in acelasi partid".

Date de iesire
Fisierul de iesire politics.out va contine pe prima linie un numar natural nr, reprezentand numarul minim de partide care vor forma coalitia. Pe cea de a doua linie vor fi scrise nr numere naturale, separate prin cate un spatiu, reprezentand numerele de identificare ale presedintilor partidelor din coalitie.

Restrictii

0 < n <= 1000
0 < m <= 50000

Exemple

politics.in politics.out Explicatie

11 7
1 2
1 11
4 5
5 9
4 7
4 9
3 10

 2
1 4		 Partidul cu presedintele 1 este reprezentat de parlamentarii 1, 2, si 11.
Partidul cu presedintele 4 este reprezentat de parlamentarii 4, 5, 7 si 9.
In total in coalitie sunt 7 parlamentari, deci coalitia este majoritara.

Timp maxim de executie/test: 0.1 secunde

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com