Програмчлалын олимпиадын бодлогын архив

КтМС өөрийн вэб сайтыг (website) шинэчлэхээр шийджээ (маш удаан хугацааны дараа). Сургуулийн багш нар олон вэб хуудас хийсэн боловч тэдгээр нь хоорондоо маш буруу холбогдсон байгааг вэбмастер нь нэг шил пиво уусныхаа дараа ажиглажээ. Вэб хуудас (webpage) бүр сургуулийн вэб сайтын өөр нэг вэб хуудсыг заах холбоосыг (link) агуулна. Вэб сайтын зочин Нүүр хуудаснаас эхлэн маш олон хуудсыг дамжиж байж хүссэн хуудсандаа хүрэхээс гадна зарим вэб хуудсууд руу Нүүр хуудаснаас яагаад ч очих боломжгүй байсан нь уг сайтын маш муу дизайнтайг илтгэж байв. Эхний ээлжинд вэбмастер Нүүр хуудаснаас бүх хуудас руу аль болох түргэн очих боломжтой болгохын тулд хэд хэдэн холбоосыг нэмсэн. Шинэ холбоосууд вэбсайтын хаана ч нэмэгдсэн байж болно.
Вэбсайт нь 1-ээс N хүртлэх тоонуудаар дугаарлагдсан N ширхэг вэб хуудаснаас тогтох ба Нүүр хуудас нь 1 гэсэн дугаартай байна. Мөн хуудас бүр өөр нэг хуудас руу шилжих ганц холбоосыг агуулна. Вэбсайтын Нүүр хуудаснаас бусад хуудас бүрт Нүүр хуудаснаас эхлэн хамгийн ихдээ K холбоосыг ашиглан очиж болдог бол уг вэбсайтыг K - холбоост вэбсайт гэж нэрлэе.
Вэбсайтын бүтэц болон K бүхэл тоог ашиглан уг вэбсайтыг K-холбоост болгоход шаардлагатай шинэ холбоосуудын хамгийн бага утгыг олох програм бич.

Input

Оролтын эхний мөрөнд вэб хуудаснуудын нийт тоо N болон дамжин өнгөрч болох холбоосуудын хамгийн их тоо болох K тоонууд өгөгдөнө (2 ≤ N ≤ 500 000, 1 ≤ K ≤ 20 000).
Дараагийн N ширхэг мөр бүрт A, B хоёр тоо зайгаар тусгаарлагдан байрлах ба энэ нь A-р хуудсанд байгаа холбоос нь B хуудасанд хүргэхийг илэрхийлнэ.

Output

Гаралтанд байх ёстой ганц бүхэл тоо нь K-холбоост вэбсайт үүсгэхийн тулд хамгийн багадаа хэдэн шинэ холбоос нэмэхийг заана.

Example

Input:
8 3
1 2
2 3
3 5
4 5
5 6
6 7
7 8
8 5

Output:
2

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

Output:
3