Задачі
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мальне.
Формат вхiдних даних
Перший рядок м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$ .
Формат вихiдних даних
Виведiть мiнiмальне $k$, або $−1$, якщо такого шляху немає.
Пояснення
- У першому прикладi можна вибрати послiдовнiсть вершин $1, 2, 3$.
- У другому прикладi це зробити неможливо.
- У третьому прикладi можна вибрати $11, 9, 7$.
Вхідні дані #1
4 3 1 2 1 2 3 2 2 4 4
Вихідні дані #1
3
Вхідні дані #2
3 3 1 2 1 2 3 1
Вихідні дані #2
-1
Вхідні дані #3
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
3