#include<iostream>
#include<vector>
#include<fstream>
#include <queue>

using namespace std;

ifstream fin("cezar.in");

ofstream fout("cezar.out");

int n, k, sediu, scadere, conditie = 0;

vector<int> auxEliminare;

vector<int> elimCoada;

struct muchie
{

    int val, origine, nrMuchii;

    muchie(int val, int origine, int nrMuchii)
        : val(val), origine(origine), nrMuchii(nrMuchii)
    {
    }
};

struct comp
{
    bool operator()(muchie const& p1, muchie const& p2)
    {
        return p1.nrMuchii < p2.nrMuchii;
    }

};

void GasireSediu(vector<int>& origine, vector<vector<int> > liste, vector<int> grad, int GradMax, vector<int>& coada, vector<int>& StocareNoduri)
{
    while (GradMax > 1)
    {
        GradMax = 0;

        for (int i = 0; i < coada.size(); i++)
            if (grad[coada[i]] == 1)
            {
                int primElLista = liste[coada[i]][0], el = coada[i], gra = grad[el], aux;

                auxEliminare.push_back(primElLista);

                origine[el] = primElLista;

                grad[el] = 0;

                StocareNoduri[primElLista] += StocareNoduri[el] + 1;

                for (int j = 0; j < liste[primElLista].size(); j++)
                    if (liste[primElLista][j] == el)
                    {
                        liste[primElLista].erase(liste[primElLista].begin() + j);

                        break;
                    }


                aux = StocareNoduri[primElLista];///afisare doar

                elimCoada.push_back(i);
            }

        for (int i = auxEliminare.size() - 1; i >= 0; i--)///scad gradul dupa ce am parcurs elementele
        {
            int g = auxEliminare[i], h = grad[auxEliminare[i]];

            grad[auxEliminare[i]]--;

            h = grad[auxEliminare[i]];

            auxEliminare.pop_back();
        }

        for (int i = elimCoada.size() - 1; i >= 0; i--)///elimin el cu grad 1
        {
            int ui = coada[elimCoada[i]], jj = elimCoada[i];

            coada.erase(coada.begin() + elimCoada[i]);

            ui = coada[elimCoada[i]];

            elimCoada.pop_back();
        }

        for (int i = 0; i < coada.size(); i++)///recalculez gradul maxim
            if (grad[coada[i]] > GradMax)
                GradMax = grad[coada[i]];
    }

    GradMax = 0;

    if (coada.size() == 1)
        sediu = coada.back();

    else
        for (int i = 0; i < coada.size(); i++)
            if (StocareNoduri[coada[i]] > GradMax)
            {
                GradMax = StocareNoduri[coada[i]];

                origine[coada[i]] = liste[coada[i]][0];

                sediu = coada[i];
            }
}

int verificare(int el, int l, vector<int> origine, vector<vector<int> > mat)
{
    for (int i = 0; i < mat[l].size(); i++)
        if (mat[l][i] == origine[el] || origine[mat[l][i]] == el)
            return 1;


    return 0;
}

void afisare(vector<int> sumaSirt, int nrSiruri)
{
    for (int i = 1; i <= nrSiruri; i++)
        cout << sumaSirt[i] << "\n";
    cout << "-----------------------------------------------\n";
}

void adaugare(vector<int> origine, priority_queue<muchie, vector<muchie>, comp> pCoada)
{
    vector<vector<int> > mat(n + 1, vector<int>());

    vector<int> sumaSir(n + 1, -1);

    int nrSiruri = 0, Smax = 0, maxim = 0;

    muchie el = pCoada.top();

    pCoada.pop();

    mat[1].push_back(el.val);

    sumaSir[1] = 0;

    nrSiruri++;

    while (!pCoada.empty())
    {
        //afisare(sumaSir, nrSiruri);

        Smax = -1;

        maxim = 0;

        el = pCoada.top();

        if (el.nrMuchii == 0 && conditie == 1)
            break;

        pCoada.pop();

        for (int i = 1; i <= nrSiruri; i++)
            if (mat[i].size() <= k && Smax < sumaSir[i] && verificare(el.val, i, origine, mat))
            {
                maxim = i;

                Smax = sumaSir[i];
            }

        if (maxim != 0)
        {
            nrSiruri++;

            mat[maxim].push_back(el.val);

            sumaSir[nrSiruri] = sumaSir[maxim];

            sumaSir[maxim] += el.nrMuchii + 1;///+1 pt ca profita si nodul curent, nu doar cele din subordinea lui

            if (sumaSir[maxim] > scadere)
                scadere = sumaSir[maxim];

            for (int i = 0; i < mat[maxim].size() - 1; i++)
                mat[nrSiruri].push_back(mat[maxim][i]);
        }

        if (maxim == 0)
        {
            nrSiruri++;

            mat[nrSiruri].push_back(el.val);

            if (el.val != sediu)
                sumaSir[nrSiruri] = el.val + 1;

            else
                sumaSir[nrSiruri] = 0;
        }

        if (mat[maxim].size() == k + 1)
            conditie = 1;

        //afisare(sumaSir, nrSiruri);
    }
}

void dikstra(vector<vector<int> >& liste)
{
    queue<int>drum;

    vector<int> distanta(n + 1, 2147483646);

    distanta[sediu] = 0;

    drum.push(sediu);

    while (!drum.empty())
    {
        int top = drum.front();

        for (int i = 0; i < liste[top].size(); i++)
            if (distanta[liste[top][i]] > distanta[top] + 1)
            {
                distanta[liste[top][i]] = distanta[top] + 1;

                drum.push(liste[top][i]);
            }

        drum.pop();
    }

    int S = 0;

    for (int i = 1; i <= n; i++)
        if (distanta[i] != 2147483646)
            S += distanta[i];

    fout << S - scadere;
}

int main()
{
    fin >> n >> k;

    int a, b, GradMax = 0;

    vector<int> grad(n + 1, 0);

    vector<int> StocareNoduri(n + 1, 0);

    vector<int> origine(n + 1, 0);

    vector<int> vecinSediu(n + 1, 0);

    vector<int> coada(n);

    for (int i = 0; i < n; i++)
        coada[i] = i + 1;

    vector<vector<int> > liste(n + 1, vector<int>());

    while (fin >> a >> b)
    {
        liste[a].push_back(b);

        liste[b].push_back(a);

        grad[a]++;

        grad[b]++;

        if (grad[a] > GradMax || grad[b] > GradMax)
            GradMax = max(grad[b], grad[a]);
    }

    GasireSediu(origine, liste, grad, GradMax, coada, StocareNoduri);

    priority_queue<muchie, vector<muchie>, comp> pCoada;

    for (int i = 1; i <= n; i++)
    {
        muchie x(i, origine[i], StocareNoduri[i]);

        pCoada.push(x);
    }

    adaugare(origine, pCoada);

    //cout << "sediu " << sediu << "\n";

    dikstra(liste);
}