ndap

Numarul de arbori partiali

== include(page="template/taskheader" task_id="ndap") ==

Poveste si cerinta...

Fie $G = (V, E)$ un graf neorientat unde V este multimea varfurilor, si E inclus in $VxV$ (produs cartezian dintre $V$ si $V$) este multimea de muchii. Definim arborele partial a lui $G$ un graf $A = (V, E')$ astfel incat $E'$ este inclus in $E$, iar intre oricare doua noduri din $V$ exista exact un drum.
 
Danduse un graf neorient, G, se cere sa se determine numarul de arbori partiali a grafului.

h2. Date de intrare

...

Pe prima linie din fisierul de intrare $ndap.in$ contine doua numere $N$ si $M$ reprezentand numarul de noduri, respectiv numarul de muchii din graful G. In continuare in fisier se vor afla $M$ linii ce descriu muchiile grafului. Pe linia $i+1$, cu $1 ≤ i ≤ M$, se vor afla doua numere $a~i~ b~i~$ cu semnificatia ca exista o muchie de la $a~i~$ la $b~i~$ in $G$.

h2. Date de iesire

...

In fisierul de iesire $ndap.out$ se va scrie pe prima linie numarul cerut in enunt modulo 30103.

h2. Restrictii

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

* $ 1 ≤ N ≤ 15 $
* $ 0 ≤ a~i~, b~i~ ≤ N-1 $
* o muchie va aparea cel mult o data i fisierul de intrare

h2. Exemplu