06. Ксения и дерево#

📝 Условие#

В дереве изначально красная только вершина 1. Запросы: покрасить вершину в красный; найти расстояние от вершины до ближайшей красной.

📥 Входные данные#

В первой строке два числа n и m (2 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁵). Далее n − 1 строк — рёбра дерева. Далее m строк t v: t = 1 — покрасить вершину v в красный, t = 2 — запрос расстояния от v до ближайшей красной. Изначально красная только вершина 1.

📤 Выходные данные#

Для каждого запроса типа 2 — ответ на отдельной строке.

🧪 Тесты#

Тест 1#

Ввод:

5 4
1 2
2 3
2 4
4 5
2 1
2 5
1 2
2 5

Вывод:

0
3
2

Тест 2#

Ввод:

3 3
1 2
2 3
2 3
1 3
2 2

Вывод:

2
1

Заметка

Оригинальное условие и проверка решения на всех тестах — по ссылке на источник.

💡 Подсказка#

⬅️ К списку задач уровня