În Roma antică există n așezări senatoriale distincte, câte una pentru fiecare dintre cei n senatori ai Republicii. Așezările senatoriale sunt numerotate de la 1 la n, între oricare două așezări existând legături directe sau indirecte. O legătură este directă dacă ea nu mai trece prin alte așezări senatoriale intermediare. Edilii au pavat unele dintre legăturile directe dintre două așezări (numind o astfel de legătură pavată stradă), astfel încât între oricare două așezări senatoriale să existe o singură succesiune de străzi prin care se poate ajunge de la o așezare senatorială la cealaltă.

Toţi senatorii trebuie să participe la şedinţele Senatului. In acest scop, ei se deplasează cu lectica. Orice senator care se deplasează pe o stradă plăteşte 1 ban pentru că a fost transportat cu lectica pe acea stradă.

Exemplu

cezar1.in

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

cezar1.out

11

Explicație

Costul minim se obţine, de exemplu, pentru alegerea celor 3 străzi între aşezările 5-7, 7-8, 8-10 și a sălii de şedințe a Senatului în aşezarea 8 (după cum este evidenţiat în desen). Există şi alte alegeri pentru care se obţine soluţia 11.

#include <bits/stdc++.h>

using namespace std;

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

int n , m , x , y , D[10001] , C[10001] , k , mini , c;
vector <int> G[10001];

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

    while(m > k)
    {
        mini = 10001;
        for(int i = 1 ; i <= n ; i++)
            if(D[i] == 1 && C[i] < mini) mini = C[i];

        for(int i = 1 ; i <= n && m > k; i++)
            if(D[i] == 1 && C[i] == mini)
            {
                D[i]--;
                c += C[i];
                for(auto p : G[i])
                    C[p] += C[i] , D[p]--;
                m--;
                //cout << i << endl;
            }
    }
    cout << c;


}