prietenie

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

Cerință

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 $31 \ 333$.

Restricții și precizări

• $1 \leq N \leq 5 \ 000$
• $0 \leq M \leq \frac{N}{2}$
• $1 \leq x, y \leq N$
• Fie două perechi $(x, y)$ şi $(a, b)$ dintre cele $M$. Atunci $x$, $y$, $a$, $b$ sunt distincte două câte două.

Exemplu

prietenie.in

3 1
1 3

prietenie.out

3

Explicație

Cele $3$ variante sunt:

• nimeni nu e prieten cu nimeni;
• $1$ prieten cu $2$;
• $2$ prieten cu $3$.