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:
 
* dacă persoana $x$ este prietenă cu persoana $y$, atunci şi persoana $y$ este prietenă cu persoana $x$;
* dacă persoana $x$ este prietenă cu persoana $y$ şi persoana $y$ este prietenă cu persoana $z$ atunci persoana $x$ este prietenă cu persoana $z$;
* 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
table(example). |_. prietenie2.in |_. prietenie2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|3 1
1 3
|3

|
h3. Explicaţie

...

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

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

5666