Fişierul intrare/ieşire:	module.in, module.out	Sursă	Lot Arad 2011
Autor	Mugurel Ionut Andreica	Adăugată de	Andrei Parvu •andrei.12
Timp execuţie pe test	0.525 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Module

Se dă un graf neorientat cu N noduri (numerotate de la 1 la N) şi M muchii. Vom defini A(i,j) = 1 dacă nodurile i şi j sunt adiacente (există o muchie între ele), respectiv A(i,j) = 0 dacă nodurile i şi j nu sunt adiacente.
O submulţime S de noduri ale grafului se numeşte modul dacă îndeplineşte următoarea condiţie: oricare ar fi trei noduri x, y si z astfel incat x ∈ S, y ∈ S si z ∉ S, avem A(x, z) = A(y, z).
Mai exact, pentru orice nod z din afara mulţimii S, ori toate nodurile din S sunt adiacente cu z, ori niciun nod din S nu este adiacent cu z. Câteva exemple simple de module sunt: mulţimea vidă, mulţimea tuturor nodurilor grafului, mulţimile ce constau din câte un singur nod al grafului.
Determinaţi numărul de module ale grafului dat, modulo 34949.

Date de intrare

Prima linie a fişierului de intrare module.in conţine numerele întregi N şi M, separate printr-un spaţiu. Următoarele M linii conţin câte două numere întregi i şi j, separate printr-un spaţiu, având semnificaţia că există o muchie între nodul i şi nodul j în graf.

Date de ieşire

În fişierul de ieşire module.out veţi afişa numărul de module ale grafului dat, modulo 34949.

Restricţii

• 1 ≤ N ≤ 100
• 0 ≤ M ≤ N * (N - 1) / 2
• 1 ≤ i, j ≤ N
• i ≠ j
• În fişierul de intrare nu se vor repeta muchii.

Exemplu

Explicaţie

Cele 14 module sunt:
{}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {1,6}, {2,3}, {2,7}, {3,7}, {2,3,7}, {1,2,3,4,5,6,7}.

Cum se trimit solutii?