Fie un graf neorientat cu N noduri și M muchii, care NU este conex.

Cerința

Să i se adauge grafului un număr minim de muchii, astfel încât acesta să devină conex. Fie extrai numărul de muchii nou-adăugate care sunt incidente cu nodul i, iar max_extra cea mai mare dintre valorile extra1, extra2,… , extraN. Mulțimea de muchii adăugate trebuie să respecte condiția ca valoarea max_extra să fie minimă.

Date de intrare

Pe prima linie a fișierului de intrare conexidad.in se află două numere naturale N și M, iar pe fiecare dintre următoarele M linii se află câte o pereche de numere a, b, semnificând faptul că există muchia [a,b]. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire conexidad.out va conține pe prima linie valoarea max_extra. Pe a doua linie va conține valoarea K reprezentând numărul de muchii nou-adăugate în graf. Fiecare dintre următoarele K linii va conține câte o pereche de numere c, d, separate prin câte un spațiu, semnificând faptul că se adaugă grafului muchia [c,d].

Restricții și precizări

• 1 ≤ N ≤ 100
• 0 ≤ M ≤ N*(N-1)/2
• Nodurile grafului sunt numerotate de la 1 la N inclusiv.
• Muchiile prezente în fișierul de intrare sunt distincte.
• Pentru orice muchie [a,b] aflată în fișierul de intrare, avem a ≠ b.
• Graful din fișierul de intrare nu este conex.
• În cazul în care soluția afișată pentru un anumit test conectează graful cu număr minim de muchii, dar nu minimizează valoarea lui max_extra, se vor acorda 50% din punctajul pentru testul respectiv.
• Dacă există mai multe soluții optime, se va admite oricare dintre acestea.
• În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru exemplele din enunț.

Exemplul 1:

conexidad.in

4 2
1 2
4 2

conexidad.out

1
1
3 1

Explicație

Graful este format din două componente conexe, cu noduri din mulțimea {1, 2, 4} respectiv nodul izolat 3. După adăugarea muchiei (3,1) vom avea valorile extra1=1, extra2=0, extra3=1, extra4=0, deci max_extra = 1. Se poate demonstra că nu există soluție cu max_extra < 1.

Exemplul 2:

conexidad.in

5 1
3 4

conexidad.out

2
3
1 3
2 3
4 5

Explicație

Graful este format din patru componente conexe, cu noduri din mulțimea {3, 4}, respectiv nodurile izolate 1, 2 și 5. După adăugarea muchiilor (1,3), (2,3) și (4,5), vom avea valorile extra1=1, extra2=1, extra3=2, extra4=1, extra5=1, deci max_extra = 2. Se poate demonstra că nu există soluție cu max_extra < 2.

#include <bits/stdc++.h>

using namespace std;

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

struct muchie
{
    int i , j;
}M[101];

vector <int> G[101];
int n , m , C[101] , nc , P[101] , maxip , V[101];

void dfs(int v , int c)
{
    C[v] = c;
    for(int i :G[v])
        if(!C[i]) dfs(i , c);
}

void dfculoare(int v , int c1 , int c2)
{
    C[v] = c2;
    for(int i :G[v])
        if(C[i] == c1) dfculoare(i , c1 , c2);
}

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= m ; i++)
    {
        int x , y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
        V[x]++;
        V[y]++;
    }
    for(int i = 1 ; i <= n ; i++)
    {
        if(!C[i])
        {
            nc++;
            dfs(i , nc);
        }
    }

    for(int k = 1 ; k < nc ; k++)
    {
        int x = 0 , y = 0 , mini = 999999;
        for(int i = 1 ; i < n ; i++)
            for(int j = i + 1 ; j <= n ; j++)
                if(C[i] != C[j] && P[i] == 0 && P[j] == 0 && V[i] != 0 && V[j] != 0)
                {
                    x = i;
                    y = j;
                    i = n + 1 , j = n + 1;
                }
            if(x == 0)
            {
                for(int i = 1 ; i < n ; i++)
                    for(int j = i + 1 ; j <= n ; j++)
                        if(C[i] != C[j] && (P[i] < mini || P[j] < mini) && (V[i] != 0 || V[j] != 0))
                        {
                            mini = max(P[i] , P[j]);
                            x = i;
                            y = j;
                        }
            }

            if(x == 0)
            {
                for(int i = 1 ; i < n ; i++)
                    for(int j = i + 1 ; j <= n ; j++)
                        if(C[i] != C[j] && (P[i] < mini || P[j] < mini))
                        {
                            mini = max(P[i] , P[j]);
                            x = i;
                            y = j;
                        }
            }
            P[x]++;
            P[y]++;
            M[k] = {x , y};
            G[x].push_back(y);
            G[y].push_back(x);
            dfculoare(y , C[y] , C[x]);
    }
    for(int i = 1 ; i <= n ; i++)
        if(P[i] > maxip) maxip = P[i];

    cout << maxip << '\n' << nc - 1 << '\n';
    for(int i = 1 ; i < nc ; i++)
        cout << M[i].i << " " << M[i].j << '\n';
}