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 şi z astfel încât x aparţine lui S, y aparţine lui S şi z nu aparţine lui 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.
Cerinţă
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 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.
Exemple
module.in
module.out
Explicaţii
7 11
5 1
5 6
1 2
1 3
1 7
6 2
6 3
6 7
4 2
4 3
4 7
14
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}.