În orașul Nicăieri există N băieți răi. Se știe că între ei există M relații de prietenie. De-a lungul timpului, aceste prietenii au dus la apariția unor “găști”. Dacă doi băieți nu sunt prieteni dar au cel puțin un prieten comun spunem că “se cunosc”. Dacă doi băieți au cel puțin o cunoștință comună, atunci și ei se cunosc.
O gașcă este un grup de băieți cu proprietatea că oricare ar fi doi băieți x și y din grup, aceștia “se cunosc”.

Cerința

Arpsod, știe exact cine este prieten cu cine și, fiind singurul băiat bun din oraș, și-a pus următoarele întrebări:

Exemplu

gasti.in

5 3
1 2
2 3
3 1

gasti.out

3 6

Explicație

Există 3 găști în oraș, formate:

Gașca 1: 1, 2, 3
Gașca 2: 4
Gașca 3: 5

Sunt 6 moduri de a face o relație de prietenie astfel încât gașca obținută să aibă număr maxim de membri

4 cu 1, 4 cu 2, 4 cu 3, 5 cu 1, 5 cu 2, 5 cu 3

#include <bits/stdc++.h>

using namespace std;

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

#define mod 666013
int n , m , x , y , v[100001] , cnt , f[100001] , maxi , maxi2 , fmaxi , fmaxi2;
vector <int> G[100001];

void dfs(int nod, int cnt)
{
   v[nod] = cnt;
   for(auto i : G[nod])
        if(!v[i]) v[i] = cnt , dfs(i , cnt);
}

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

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

    ///cer 1
    cout << cnt << ' ';

    ///cer 2

    for(int i = 1 ; i <= n ; i++)
        f[v[i]]++;

    for(int i = 1 ; i <= n ; i++)
        if(f[i] > maxi) maxi = f[i];

    for(int i = 1 ; i <= n ; i++)
        if(f[i] == maxi) fmaxi++;

    if(fmaxi > 1)
    {
        cout << 1ll * fmaxi * (fmaxi - 1) / 2 % mod * maxi % mod * maxi % mod;
    }
    else
    {
        for(int i = 1 ; i <= n ; i++)
            if(f[i] > maxi2 && f[i] != maxi) maxi2 = f[i];
        for(int i = 1 ; i <= n ; i++)
            if(f[i] == maxi2 && f[i] != maxi) fmaxi2++;
        cout << 1ll * fmaxi2 % mod * maxi % mod * maxi2 % mod;
    }

}