Module

module

== include(page="template/taskheader" task_id="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*.

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$

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

Fişierul de intrare $module.in$ ...

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

În fişierul de ieşire $module.out$ ...

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

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. module.in |_. module.out |

| 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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

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

...

== include(page="template/taskfooter" task_id="module") ==

5672