| Fişierul intrare/ieşire: | prietenie2.in, prietenie2.out | Sursă | Lot Arad 2011 |
| Autor | Andrei Parvu | Adăugată de |  Mihai Calancea •klamathix |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Prietenie2
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.
Cerinta
Să se scrie un program care să calculeze numărul total de relaţii de prietenie posibile.
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.
Date de ieşire
Fisierul prietenie.out conţine pe singura sa linie numărul total de prietenii posibile modulo 31333.
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ă.
Exemplu
| prietenie2.in | prietenie2.out |
|---|---|
| 3 1 1 3 | 3 |
Explicaţie
Cele 3 variante sunt:
- nimeni nu e prieten cu nimeni;
- 1 prieten cu 2;
- 2 prieten cu 3.
