Назовем неориентированный связный граф из n вершин и n - 1 ребра бородой, если в нем все вершины кроме, возможно, одной имеют степень 2 или 1 (то есть в нем существует не более одной вершины, степень которой более двух). Напомним, что степень вершины — это количество инцидентных ей ребер.
Пусть каждое ребро имеет либо черный цвет, либо белый, изначально все ребра имеют черный цвет.
Вам дано описание графа-бороды. Ваша задача — обрабатывать запросы следующих типов:
Вершины пронумерованы целыми числами от 1 до n, а ребра — целыми числами от 1 до n - 1.
Первая строка входных данных содержит целое число n (2 ≤ n ≤ 105) — количество вершин в графе. Далее в n - 1 строках заданы ребра номерами вершин vi, ui (1 ≤ vi, ui ≤ n, vi ≠ ui), которые данное ребро соединяет. Гарантируется, что заданный граф связен и образует граф-бороду, а также не содержит петель и кратных ребер.
Следующая строка содержит целое число m (1 ≤ m ≤ 3·105) — количество запросов. Следующие m строк содержат запросы в формате: первым в строке записано целое число type, которое принимает значения от 1 до 3 и означает тип запроса.
Если type = 1, то текущий запрос — это запрос на покраску ребра в черный цвет. В этом случае в строке кроме числа type содержится целое число id (1 ≤ id ≤ n - 1), означающее номер ребра, которое нужно покрасить.
Если type = 2, то текущий запрос — это запрос на покраску ребра в белый цвет, его формат аналогичен предыдущему запросу.
Если type = 3, то текущий запрос — запрос нахождения расстояния. В этом случае в строке кроме числа type содержатся два целых числа a, b (1 ≤ a, b ≤ n, a может быть равно b) — номера вершин, расстояние между которыми надо найти.
Числа во всех строках разделены ровно одним пробелом. Ребра нумеруются в том порядке, в котором они заданы во входных данных.
Для каждого запроса «найти расстояние между вершинами a и b» выведите результат. Если данные вершины на момент запроса недостижимы друг из друга по черным ребрам, то выведите «-1» (без кавычек). Результаты выводите в порядке поступления запросов, числа разделяйте пробелами или переводами строк.
3
1 2
2 3
7
3 1 2
3 1 3
3 2 3
2 2
3 1 2
3 1 3
3 2 3
1
2
1
1
-1
-1
6
1 5
6 4
2 3
3 5
5 6
6
3 3 4
2 5
3 2 6
3 1 2
2 3
3 3 1
3
-1
3
2
В первом примере вершины 1 и 2 связаны ребром номер 1, а вершины 2 и 3 — ребром номер 2. До перекраски ребра номер 2 каждая вершина достижима из каждой по черным ребрам, в частности, кратчайший путь между 1 и 3 проходит через оба ребра.
Если перекрасить ребро номер 2 в белый цвет, то вершина 3 оказывается отрезанной от остальных, то есть из нее не существует пути по черным ребрам ни в какую другую вершину.
| Codeforces Round 112 (Div. 2) |
|---|
| Закончено |
