eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Пошук у ширину 0-1

Пошук у ширину 0-1

Ліміт часу 3 секунди
Ліміт використання пам'яті 128 MiB

Дано неорієнтований граф. Вага його ребер може приймати тільки значеня 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
Автор Михаил Медведев