Чередование цветов


Отправить решение Решать в редакторе

Сложность: 40%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Чередование цветов

В графе n вершин. Даны красные и синие направленные рёбра (между парой вершин могут быть и красные, и синие рёбра, возможны петли). Для каждой вершины найдите длину кратчайшего пути из вершины 1, в котором цвета рёбер строго чередуются (первое ребро любого цвета).

Ввод. В первой строке n, r, b (1 ≤ n ≤ 10⁵, 0 ≤ r, b ≤ 10⁵). Далее r строк a c — красные рёбра a → c, затем b строк — синие.

Вывод. n чисел через пробел: длина пути или -1. Для вершины 1 ответ 0.

Пример 1

Ввод

4 2 2
1 2
2 3
1 3
3 4

Вывод

0 1 1 -1

Комментарии

Еще нет ни одного комментария.