D. Граф-борода
ограничение по времени на тест
4 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Назовем неориентированный связный граф из n вершин и n - 1 ребра бородой, если в нем все вершины кроме, возможно, одной имеют степень 2 или 1 (то есть в нем существует не более одной вершины, степень которой более двух). Напомним, что степень вершины — это количество инцидентных ей ребер.

Пусть каждое ребро имеет либо черный цвет, либо белый, изначально все ребра имеют черный цвет.

Вам дано описание графа-бороды. Ваша задача — обрабатывать запросы следующих типов:

  • покрасить в черный цвет ребро, которое в описании имеет номер i (гарантируется, что к моменту этого запроса i-ое ребро имеет белый цвет)
  • покрасить в белый цвет ребро, которое в описании имеет номер i (гарантируется, что к моменту этого запроса i-ое ребро имеет черный цвет)
  • найти длину кратчайшего пути только по черным ребрам между вершинами a и b или указать, что не существует такого пути между ними (длина пути — это количество ребер в нем)

Вершины пронумерованы целыми числами от 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 оказывается отрезанной от остальных, то есть из нее не существует пути по черным ребрам ни в какую другую вершину.