Tipul $A$
Secventa grafurilor de tip $A$ se construieste in modul ce se poate deduce din exemplele urmatoare:

   $A1$ $A2$ $A3$ $A4$        $A5$

     $A1$        $A2$       $A3$            $A4$        $A5$

!problema/perfect?poza1.jpg!

Tipul $B$
Secventa grafurilor de tip $B$ se construieste dupa modelul urmator:

       $B1$  $B2$    $B3$      $B4$

     $B1$        $B2$       $B3$            $B4$

!problema/perfect?poza2.jpg!

Se numeste cuplaj perfect in graf o modalitate de a alege muchii ale grafului astfel incat oricare varf din graf sa fie incident cu exact o muchie aleasa. Doua cuplaje sunt distincte daca exista o muchie care apartine unui cuplaj, dar nu apartine celuilalt.

h2. Cerinta
 
Dat fiind un graf de unul dintre tipurile din enunt, sa se determine numarul de cuplaje perfecte distincte ale grafului respectiv.
 
 

h2. Date de intrare

Fisierul de intrare $perfect.in$ ...

Fisierul de intrare $perfect.in$ contine o singura linie pe care se afla un caracter si un numar natural nenul $n$, separate printr-un spatiu. Caracterul poate fi $A$, $B$ sau $C$ si indica tipul grafului. Numarul natural $n$ indica numarul de ordine al grafului in secventa de grafuri de tipul specificat de caracter.

h2. Date de iesire

In fisierul de iesire $perfect.out$ ...

Fisierul de iesire $perfect.out$ va contine o singura linie pe care va fi scris numarul de cuplaje perfecte ale grafului din fisierul de intrare.

h2. Restrictii

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

* $1 ≤ n ≤ 100$

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

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

| A 4
| 5
|
| B 2
| 4
|
| C 2
| 8
|

h3. Explicatie

...

Cele $5$ cuplaje perfecte ale grafului $A4$ sunt:
 
img 1
 
Cele $4$ cuplaje perfecte ale grafului $B2$ sunt:
 
img 2
 
Cele $8$ cuplaje perfecte ale grafului $C2$ sunt:
 
img 3

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