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

Marcel a invatat despre forme. Formele pot fi rotunde sau complicate. Lui Marcel ii place ca atunci cand sunt complicate, macar sa fie mici, asa, cat mai irelevante. Spre exemplu un graf poate avea mai multe componente biconexe, fiecare dintre ele fiind reprezentabile fie sub forma unui ciclu simplu rotund elegant, fie este de marime foarte mica.

Marcel a invatat despre forme. Formele pot fi rotunde sau complicate. Lui Marcel ii place ca atunci cand sunt complicate, macar sa fie mici, asa, cat mai irelevante. Spre exemplu un graf poate avea mai multe componente biconexe, fiecare dintre ele fiind fie reprezentabila sub forma unui ciclu simplu rotund elegant, fie de marime foarte mica.

Astfel, un graf sclifosit este unul neorientat si conex, in care nodul $1$ are gradul egal cu $1$, si toate componentele sale biconexe fie sunt reprezentabile sub forma unui ciclu simplu fara alte muchii intre nodurile respective, fie contin maxim $8$ noduri.

Astfel, un graf sclifosit este unul neorienta, conex, fara muchii duble sau muchii de la un nod la acelasi nod, in care nodul $1$ are gradul egal cu $1$ (prin urmare graful are macar $2$ noduri), si toate componentele sale biconexe fie sunt reprezentabile sub forma unui ciclu simplu fara alte muchii intre nodurile respective, fie contin maxim $8$ noduri.

Determinati in cate moduri se poate partitiona un graf sclifosit in doua subgrafuri nevide conexe.
h2. Date de intrare

Fişierul de intrare $sclifoseala.in$ contine pe prima linie numarul $T$ de teste. Structura fiecarui test e urmatoarea: Prima linie contine numarul $N$ de noduri, respectiv $M$ de muchii. Urmatoarele M linii contin perechi de numere naturale $a$ si $b$ reprezentand faptul ca exista o muchie de la $a$ la $b$.

Fişierul de intrare $sclifoseala.in$ contine pe prima linie numarul $T$ de teste. Structura fiecarui test e urmatoarea: Prima linie contine numarul $N$ de noduri, respectiv $M$ de muchii. Urmatoarele $M$ linii contin perechi de numere naturale $a$ si $b$ reprezentand faptul ca exista o muchie bidirectionala de la $a$ la $b$.

h2. Date de ieşire

În fişierul de ieşire $sclifoseala.out$ se va afla un singur numar, si anume numarul de partitionari ale grafului dat in doua subgrafuri nevide conexe.

În fişierul de ieşire $sclifoseala.out$ se va afla un singur numar pentru fiecare din cele $T$ teste, si anume numarul de partitionari ale grafului dat in doua subgrafuri nevide conexe.

h2. Restricţii
* $1 ≤ T ≤ 3$

* $1 ≤ a, b ≤ N, M ≤ 30.000$

* $1 ≤ a, b ≤ N ≤ 30.000$

*h2. Precizare

h2. Punctare

* Daca sunteti curiosi sa aflati ce este aceea o componenta biconexa, Marcel va recomanda sa invatati: http://www.infoarena.ro/problema/biconex

Pentru evaluare se vor utiliza $5$ teste, fiecare valorand $20$ de puncte. O parte din ele contin urmatoarele restrictii suplimentare:
 
* in primul test, $N ≤ 15$
* in al doilea test, exista o singura componenta biconexa sub forma unui ciclu simplu, iar restul au cate 2 noduri
* in al treilea test, componenentele biconexe sunt fie de marime $2$, fie sub forma unui ciclu simplu
* in al patrulea test, componentele biconexe contin cel mult $8$ noduri
* in al cincilea test, nu exista restrictii suplimentare
 
h2. Precizari
 
* Daca sunteti curiosi sa aflati ce este aceea o componenta biconexa, Marcel va recomanda sa invatati: 'Componente biconexe':/infoarena.ro/problema/biconex
* Gradul unui nod este egal cu numarul de muchii care il contin ca varf
* Partitionarea in mutlimile A, B este diferita de partitionarea in multimile B, A (vezi exemplu)

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

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

| 2
6 6
1 2
2 3
3 4
4 5
5 6
6 2
6 9
1 2
2 3
3 4
4 5
5 6
6 2
5 3
5 2
4 6
| 22
28
|
| 1
4 4
1 2
2 3
3 4
4 2
| 8
|

h3. Explicaţie

...

Pentru al doilea exemplu, partitionarile cautate sunt:
1/234, 12/34, 123/4, 124/3, 234/1, 34/12, 4/123 3/124

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