#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

short mat[151][151];
short mem[151][151];
bool accessed[151];
short n, p, ans;

short process(short beg = 1) {
    for(int i = beg + 1; i <= n; ++i) {
        if(mat[beg][i] != 0)
            mat[beg][0] += process(i) + 1;
    }
    // mat[beg][0] means how many childs this node has. 
    return mat[beg][0];
}

short solve(short root = 1, short sum = p) {
    short& cur = mem[root][sum];
    if(cur >= 0)
        return cur;
    if(sum == 1) {
        cur = 0;
        return 0;
    }
    short ret = 0x7FFF;
    for(short i = root + 1; i <= n; ++i) {
        if(mat[root][i] == 1) {
            if(mat[i][0]+1 == sum) {//cout<<'E'<<' '<<i<<' '<<sum<<' '<<mat[i][0]<<'\n';
                ret = 1;
                break;
            }
            else if(!accessed[i] && mat[i][0] < sum) {//cout<<'G'<<' '<<i<<' '<<sum<<' '<<mat[i][0]<<'\n';
                accessed[i] = true;
                short tmp = solve(root, sum - mat[i][0] - 1);
                accessed[i] = false;
                if(0 < tmp && tmp < n)
                    ++tmp;
                else
                    continue;
                if(tmp < ret)
                    ret = tmp;
            }
            else if(mat[i][0] > sum) {//cout<<'L'<<' '<<i<<' '<<sum<<' '<<mat[i][0]<<'\n';
                short tmp = solve(i, sum);
                if(0 < tmp && tmp < n)
                    ++tmp;
                else
                    continue;
                if(tmp < ret)
                    ret = tmp;
            }
        }
    }
    cur = ret;//(ret == 0x7FFF ? 0 : ret);
    return cur;
}

int main(void) {
    ifstream fin("reroads.in");
    ofstream fout("reroads.out");
    fin >> n >> p;
    memset(mat, 0, sizeof(mat));
    memset(mem, 0xFF, sizeof(mem));
    memset(accessed, 0, sizeof(accessed));
    for(short x, y, i = 1; i <= n; ++i) {
        fin >> x >> y;
        mat[x][y] = 1;
    }
    process();
    fout << solve() - 1 << endl;
    return 0;
}