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

#include <bits/stdc++.h>


using namespace std;

int n , x , y , p[50001] , cnt;
vector <int> G[50001];
queue <int> Q;
int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
        p[x]++;
        p[y]++;
    }

    for(int i = 1 ; i <= n ; i++)
        if(p[i] == 1)Q.push(i);

    while(!Q.empty())
    {
        x = Q.front();
        for(int y : G[x])
            if(p[y])
            {
                p[y]--;
                if(p[y] == 1) Q.push(y);
            }
        p[x] = 0;
        Q.pop();
    }
    for(int i = 1 ; i <= n ; i++)
        if(p[i] == 2) cnt++;
    cout <<cnt;
}