Задачі
Пошук у ширину 0-1
Пошук у ширину 0-1
Дано неорієнтований граф. Вага його ребер може приймати тільки значеня 0 або 1. Знайдіть найкоротшу відстань між вершинами s і d.
Вхідні дані
Перший рядок містить чотири цілих числа: кількість вершин n, кількість ребер m\:(n, m \le 10^5) і номери вершин s і d\:(1 \le s, d \le n). Кожен з наступних m рядків містить три цілих числа a, b і w що задають неорієнтоване ребро (a, b) з цілочисельною вагою w\:(0 \le w \le 1).
Вихідні дані
Виведіть найкоротший шлях між вершинами s і d.
Приклад
Вхідні дані #1
5 5 1 3 1 2 0 2 3 1 3 4 0 4 5 1 1 5 1
Вихідні дані #1
1