Назовем неориентированный связный граф из n вершин и n - 1 ребра бородой, если в нем все вершины кроме, возможно, одной имеют степень 2 или 1 (то есть в нем существует не более одной вершины, степень которой более двух). Напомним, что степень вершины — это количество инцидентных ей ребер.
Пусть каждое ребро имеет либо черный цвет, либо белый, изначально все ребра имеют черный цвет.
Вам дано описание графа-бороды. Ваша задача — обрабатывать запросы следующих типов:
- покрасить в черный цвет ребро, которое в описании имеет номер i (гарантируется, что к моменту этого запроса i-ое ребро имеет белый цвет)
- покрасить в белый цвет ребро, которое в описании имеет номер i (гарантируется, что к моменту этого запроса i-ое ребро имеет черный цвет)
- найти длину кратчайшего пути только по черным ребрам между вершинами a и b или указать, что не существует такого пути между ними (длина пути — это количество ребер в нем)
Вершины пронумерованы целыми числами от 1 до n, а ребра — целыми числами от 1 до n - 1.
Выходные данные
Для каждого запроса «найти расстояние между вершинами a и b» выведите результат. Если данные вершины на момент запроса недостижимы друг из друга по черным ребрам, то выведите «-1» (без кавычек). Результаты выводите в порядке поступления запросов, числа разделяйте пробелами или переводами строк.
Примечание
В первом примере вершины 1 и 2 связаны ребром номер 1, а вершины 2 и 3 — ребром номер 2. До перекраски ребра номер 2 каждая вершина достижима из каждой по черным ребрам, в частности, кратчайший путь между 1 и 3 проходит через оба ребра.
Если перекрасить ребро номер 2 в белый цвет, то вершина 3 оказывается отрезанной от остальных, то есть из нее не существует пути по черным ребрам ни в какую другую вершину.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
|
2
|
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
|