Prietenie2

prietenie2

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

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.
 

Poveste şi cerinţă...

h2. Date de intrare

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.

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

h2. Date de ieşire

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

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

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