Rezolvare PBinfo #2888

Se consideră un graf neorientat conex cu n noduri și n muchii.

Cerința

Să se determine numărul arborilor parțiali ai grafului.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n perechi de numere naturale x y reprezentând cele n muchii.

Date de ieșire

Programul va afișa pe ecran numărul arborilor parțiali ai grafului.

Restricții și precizări

• 1 ≤ n ≤ 30.000
• cele n muchii sunt distincte două câte două

Exemplu:

Intrare

7
1 4
1 5
2 3
2 4
4 5
4 6
4 7

Ieșire

3

Explicație

Graful din exemplu corespunde imaginii de mai jos.

Primul arbore parțial este format din muchiile: (1, 4), (2, 3), (2, 4), (4, 5), (4, 6), (4, 7).
Al doilea arbore parțial este format din muchiile: (1, 4), (1, 5), (2, 3), (2, 4), (4, 6), (4, 7).
Al treilea arbore parțial este format din muchiile: (1, 5), (2, 3), (2, 4), (4, 5), (4, 6), (4, 7).