Nu exista diferente intre titluri.
Diferente intre continut:
== 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.
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.
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.
Ş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. 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 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
Fisierul prietenie.out conţine pe singura sa linie numărul total de prietenii posibile modulo 31333.
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ă.
• 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
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.