prietenie2

Prietenie2

== include(page="template/taskheader" task_id="prietenie2") ==

Poveste şi cerinţă...

Poli are la facultate N colegi. Unii dintre colegii lui Poli pot fi prieteni între ei, cu respectarea  următoarelor condiţii:
1. dacă persoana x este prietenă cu persoana y, atunci şi persoana y este prietenă cu persoana x;
2. dacă persoana x este prietenă cu persoana y şi persoana y este prietenă cu persoana z atunci persoana x este prietenă cu persoana z;
3. o persoană este tot timpul prietenă cu ea însăşi.
 
Definim o relaţie de prietenie ca fiind mulţimea prieteniilor formate între cei N colegi.
	Poli a mers prin facultate şi a reuşit să obţină de la fiecare persoană maxim o informaţie legată de cineva cu care acea persoană nu este prietenă.
	Ştiind numărul de colegi ai lui Poli şi  informaţiile pe care le-a obţinut acesta să se determine câte relaţii distincte de prietenie se pot forma care respectă informaţiile obţinute. O relaţie de prietenie este considerată diferită faţă de altă relaţie dacă există o pereche (x, y) care în prima relaţie x este prieten cu y, iar în a doua relaţie x nu este prieten cu y.
 
h2.Cerinta
 
Să se scrie un program care să calculeze numărul total de relaţii de prietenie posibile.
 

h2. Date de intrare

Fişierul de intrare $prietenie2.in$ ...

Fişierul prietenie.in conţine pe prima linie N şi M, numărul de colegi, respectiv numărul de informaţii pe care le-a obţinut Poli. Următoarele M linii conţin câte două numere (x, y) reprezentând faptul că x nu este prieten cu y.

h2. Date de ieşire

În fişierul de ieşire $prietenie2.out$ ...

Fisierul prietenie.out conţine pe singura sa linie numărul total de prietenii posibile modulo 31333.

h2. Restricţii

* $... ≤ ... ≤ ...$

•	1 ≤ N ≤ 5000
•	0 ≤ M ≤ N / 2
•	1 ≤ x, y ≤ N
•	Fie două perechi (x, y) şi (a, b) dintre cele M. Atunci x, y, a, b sunt distincte două câte două.
 

h2. Exemplu