* 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$.

	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

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ă.

•	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

h3. Explicaţie

Cele $3$ variante sunt:
 
# nimeni nu e prieten cu nimeni;
# $1$ prieten cu $2$;
# $2$ prieten cu $3$.

Cele $3$ variante sunt: $1)$ nimeni nu e prieten cu nimeni;   $2)$ $1$ prieten cu $2$;   $3)$ $2$ prieten cu $3$.

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