IOI
IOI
Знайдiть шлях, для якого виконуються такi умови:
Шлях складається з послiдовностi рiзних мiст a_1 , a_2 , . . . , a_k , таких, що мiж кожними двома сусiднiми мiстами повинно iснувати ребро.
Сумарна довжина шляху повинна бути рiвною l.
Потрiбно вибрати таку послiдовнiсть мiст, що k — мiнiмальне.
Input data
Перший рядок мiстить два цiлi числа n та l (1 ≤ n ≤ 2 · 10^5 , 1 ≤ l ≤ 10^6) — кiлькiсть мiст та потрiбна довжина.
Кожен з наступних n − 1 рядкiв мiстить три цiлi числа v_i , u_i та t_i(1 ≤ u_i , v_i ≤ n, v_i ≠ u_i , 1 ≤ t_i ≤ 10^6), що означає, що мiж мiстами v_i та u_i iснує дорога довжиною t_i .
Output data
Виведiть мiнiмальне k, або −1, якщо такого шляху немає.
####Примiтка
У першому прикладi можна вибрати послiдовнiсть вершин 1, 2, 3.
У другому прикладi це зробити неможливо.
У третьому прикладi можна вибрати 11, 9, 7.
Examples
4 3 1 2 1 2 3 2 2 4 4
3
3 3 1 2 1 2 3 1
-1
11 12 1 2 3 1 3 4 3 4 5 4 5 4 5 6 6 1 7 3 7 8 2 7 9 5 9 10 6 9 11 7
3