La cursul de comunicare organizat în vacanță, au participat N persoane, numerotate cu numere de ordine de la 1 la N. Fiecare persoană are la curs mai mulți prieteni apropiați, cărora le comunică orice informație imediat cum a aflat-o. Relaţiile de comunicare nu sunt bidirecţionale, cu alte cuvinte dacă persoana a îi transmite imediat informații persoanei b, nu este obligatoriu ca şi persoana b să transmită imediat informaţiile pe care le primeşte persoanei a.

Profesorul studiază relaţiile dintre participanţii la curs. El defineşte un nucleu de comunicare ca fiind un grup cu număr maxim de cursanţi cu proprietatea că oricare ar fi a şi b doi cursanţi din grup, dacă a primeşte o informaţie, aceasta va ajunge şi la cursantul b (direct sau prin intermediul altor cursanţi din grup).

Profesorul dorește să determine numărul de nuclee de comunicare existente la cursul său.

Cerința

Cunoscând N, numărul de cursanţi, precum și prietenii fiecărui cursant, scrieţi un program care să determine numărul de nuclee de comunicare existente.

Date de intrare

Fișierul de intrare nuclee.in conține pe prima linie un număr natural N, reprezentând numărul de cursanţi. Următoarele N linii conțin informații despre prietenii cursanţilor. Astfel, pe linia i+1 din fişier se află numerele naturale k p[1] p[2] … p[k], separate prin câte un spaţiu, unde k reprezintă numărul de prieteni ai persoanei i, iar p[1] p[2] … p[k], reprezintă prietenii persoanei i.

Date de ieșire

Fișierul de ieșire nuclee.out va conține o singură linie pe care va fi scris un singur număr natural reprezentând numărul de nuclee de comunicare existente.

Restricții și precizări

• 1 < N < 201
• Pot exista persoane care nu au prieteni apropiați.
• O persoană poate face parte dintr-un singur nucleu.
• Un nucleu poate fi format dintr-o singură persoană.

Exemplu

nuclee.in

5
2 3 4
2 1 3
1 2
0
2 1 4

nuclee.out

3

Explicație

• Persoana 1 are 2 prieteni apropiaţi (3 şi 4)
• Persoana 2 are de asemenea 2 prieteni apropiaţi (1 şi 3)
• Persoana 3 are un prieten (pe 2)
• Persoana 4 nu are prieteni.
• Persoana 5 are doi prieteni (pe 1 şi pe 4).

Există 3 nuclee de comunicare.

N1: 1, 2, 3
N2: 4
N3: 5

#include <bits/stdc++.h>


using namespace std;

ifstream cin("nuclee.in");
ofstream cout("nuclee.out");

stack <int> S;
vector <int> G[1001];
vector <int> c;
int n , x , y , v[1001] , L[1001] , cnt , inS[1001] , rez;

void tarjan(int nod)
{
    v[nod] = L[nod] = ++cnt;
    S.push(nod);
    inS[nod] = 1;
    for(auto i : G[nod])
    {
        if(!v[i]) tarjan(i) , L[nod] = min(L[nod], L[i]);
        else if(inS[i]) L[nod] = min(L[nod], v[i]);
    }

    if(v[nod] == L[nod])
    {
        c.clear();
        while(true)
        {
            int val = S.top();
            S.pop();
            c.push_back(val);
            inS[val] = 0;
            if(nod == val) break;
        }
        rez++;
    }
}

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> x;
        for(int j = 1 ; j <= x ; j++)
        {
            cin >> y;
            G[i].push_back(y);
        }
    }

    for(int i = 1 ; i <= n ; i++)
        if(!v[i]) cnt = 0 , tarjan(i);

    cout << rez;
    return 0;
}