La o nuntă sunt invitate n persoane, numerotate de la 1 la n. Se știe că o parte din ele se cunosc două câte două, fie că sunt rude, fie de la serviciu, fie sunt prieteni sau vecini. Astfel se vor forma un număr K minim de grupuri astfel încât în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut. Pentru fiecare grup de cel puțin două persoane se stabileşte un lider – persoana cu numărul de ordine minim. Aceste grupuri vor fi numerotate de la 1 la K în ordinea crescătoare a numerelor de ordine ale liderilor. Ca sa se ivească cât mai puține situații stânjenitoare, organizatorul nunții ar dori să aranjeze o masă principală cu cel puţin n/2+1 invitaţi, la care să fie aşezate unul sau mai multe astfel de grupuri întregi numerotate cu valori consecutive.

Cerința

Fiind date n, numărul de persoane, m, numărul de perechi de invitaţi care se cunosc între ei și cele m perechi, să se determine numărul K minim de grupuri formate din cel puțin doi invitați astfel încât, în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut, precum şi numărul variantelor distincte în care se poate organiza masa cu cel puţin n/2+1 invitaţi din grupurile formate.

Date de intrare

Fișierul de intrare nunta.in conține pe prima linie două numere naturale separate prin spațiu n și m, n reprezentând numărul de invitaţi, respectiv m numărul de perechi de invitaţi care se cunosc între ei. Pe fiecare din următoarele m linii se află câte două numere naturale x și y, 1≤x, y≤n, separate printr-un spațiu, cu semnificația că invitaţii x și y se cunosc între ei.

Date de ieșire

Fișierul de ieșire nunta.out va conține pe prima linie un număr natural g reprezentând numărul minim de grupuri formate din cel puțin doi invitați astfel încât, în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut. Pe cea de a doua linie va fi scris un număr natural v reprezentând numărul variantelor distincte în care se poate organiza masa cu cel puţin n/2+1 invitaţi din grupurile formate.

Restricții și precizări

• 0 < n <= 20000
• 0 < m <= 100000

Exemplul 1

nunta.in

31 6
5 7
2 3
10 14
14 6
9 15
7 30

nunta.out

4
0

Explicație

Grupurile formate din cel puțin doi invitați sunt : (2,3), (5,7,30), (6,10,14), (9,15), deci K=4. Ele nu sunt suficiente pentru a forma o masă cu cel puţin 16 invitaţi, deci sunt 0 variante de aranjare.

Exemplul 2

nunta.in

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

nunta.out

4
3

Explicație

Sunt k=4 grupuri formate din cel puțin doi invitați. Acestea sunt: G1=(1,2,3,4), G2=(5,6), G3=(7,8,10), G4=(9,12).

Variantele distincte în care se poate organiza masa cu cel puţin n/2+1, adică 7 invitaţi din grupurile formate sunt: G1+G2+G3, G1+G2+G3+G4 și G2+G3+G4. G1+G3+G4 nu este alcătuit din grupuri numerotate cu valori consecutive.

#include <bits/stdc++.h>



using namespace std;

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

int n, m, cnt, nrc, P[20001], jum, sp[10001];
vector<vector<int>> G(20001);
pair<int, int> cc[20001];

void lee(int nod){
    cnt = 1;
    P[nod] = 1;
    queue<int> Q;
    Q.push(nod);
    while(!Q.empty()){
        int x = Q.front();
        for(auto i:G[x])
            if(!P[i])
                P[i] = 1, cnt++, Q.push(i);
        Q.pop();
    }
}

bool comp(pair<int, int> a, pair<int, int> b){
    if(a.second != b.second)
        return a.second < b.second;
    return a.first < b.first;
}

int main(){
    int x, y;
    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(!P[i]){
            lee(i);
            if(cnt > 1){
                cc[++nrc].first = i;
                cc[nrc].second = cnt;
            }
        }
    jum = n / 2 + 1;
    cout << nrc << '\n';
    cnt = 0;
    for(int i = 1; i <= nrc; ++i)
        sp[i] = sp[i-1] + cc[i].second;
    int h = nrc + 1;
    for(int i = 1; i <= nrc; ++i)
        if(sp[i] >= jum && h == nrc + 1)
            h = i;
    for(int i = h; i <= nrc; ++i){
        int j = 0;
        while(sp[i] - sp[j] >= jum)
            j++;
        cnt+=j;
    }
    cout << cnt;
    return 0;
}