Cerința

Cătălin avea un singur prieten dar, fiind foarte sociabil, el se împrietenește automat cu toți prietenii prietenului său și cu prietenii prietenilor acestuia ș.a.m.d. (s-a inspirat din modelul Facebook).

Inițial, în grupul de persoane, nimeni nu are prieteni dar, pe parcursul timpului, se leagă noi relații de prietenie.

Definim două tipuri de operații:

• 1 x y – ce reprezintă faptul că x se împrietenește cu y.
• 2 p – Cătălin vă întreabă care este numărul de prieteni pe care îi poate avea, dacă inițial ar fi prieten doar cu p. Se va ține cont doar de relațiile de prietenie stabilite până în acel moment.

Date de intrare

Fișierul de intrare prieteni.in conține pe prima linie numerele N K, unde N este numărul de persoane, iar K este numărul de operații. Următoarele K linii conțin câte o operație din unul dintre tipurile de mai sus.

Date de ieșire

În fişierul de ieşire prieteni.out se găsesc răspunsurile doar la operațiile de tip 2, în ordinea în care apar în fişierul de intrare. Pe fiecare linie i va fi scris un număr, reprezentând răspunsul la a i-a întrebarea de tip 2 citită.

Restricții și precizări

• 1 < N < 1.000.000
• 1 < K < 1.000.000
• Relația de prietenie este reciprocă.

Exemplu

prieteni.in

10 10
1 6 7
1 4 5
1 10 8
2 2
1 4 8
2 9
2 4
1 8 3
2 10
2 9

prieteni.out

1
1
4
5
1

Explicație

• 1 = numărul de prieteni pe care îi va avea dacă se împrietenește cu 2 la întrebarea 2 2
• 1 = numărul de prieteni pe care îi va avea dacă se împrietenește cu 9 la întrebarea 2 9
• 4 = numărul de prieteni pe care îi va avea dacă se împrietenește cu 4 care s-a împrietenit anterior cu 5 şi 8, 8 fiind deja prieten cu 10
• ș.a.m.d.

#include <bits/stdc++.h>

using namespace std;

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

int T[1000001] , n , cer , m , t , C[1000001];

void leaga(int a , int b)
{
    if(T[a] > T[b]) T[a] = T[b] , C[b] += C[a];
    else T[b] = T[a] , C[a] += C[b];
}

int radacina(int a)
{
    if(a == T[a]) return a;
    else return T[a] = radacina(T[a]);
}
int main()
{
    cin >> n >> m;
    int x , y , c;
    for(int i = 1 ; i <= n ; i++)
        T[i] = i , C[i] = 1;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> cer;
        if(cer == 1)
        {
            cin >> x >> y;
            int r1 , r2;
            r1 = radacina(x);
            r2 = radacina(y);
            if(r1 != r2) leaga(r1 , r2);
        }
        else
        {
            cin >> x;
            cout << C[radacina(x)] << '\n';
        }

    }
}