Задачи
Эх, дороги...
Эх, дороги...
В многострадальном Тридесятом государстве опять готовится дорожная реформа. Впрочем, надо признать, дороги в этом государстве находятся в довольно плачевном состоянии. Так что реформа не повредит. Одна проблема - "дорожникам не развернуться, поскольку в стране действует жесткий закон" - из каждого города должно вести не более двух дорог. Все дороги в государстве двустронние, то есть по ним разрешено движение в обеих направлениях (разумеется, разметка отсутствует). В результате реформы некоторые дороги будут строиться, а некоторые другие закрываться на бессрочный ремонт.
Петя работает диспетчером в службе грузоперевозок на дальние расстояния. В связи с предстоящими реформами, ему необходимо оперативно определять оптимальные маршруты между городами в условиях постоянно меняющейся дорожной ситуации. В силу большого количества пробок и сотрудников полиции в городах, критерием оптимальности маршрута считается количество промежуточных городов, которые необходимо проехать.
Помогите Пете по заданной последовательности сообщений об изменении структуры дорог и запросам об оптимальном способе проезда из одного города в другой, оперативно отвечать на запросы.
\InputFile
В первой строке входного файла заданы числа \textbf{n} - количество городов, \textbf{m} - количество дорог в начале реформы и \textbf{q} - количество сообщений об изменении дорожной структуры и запросов (\textbf{1} ≤ \textbf{n}, \textbf{m} ≤ \textbf{100 000}, \textbf{q} ≤ \textbf{200 000}). Следующие \textbf{m} строк содержат по два целых числа каждая - пары городов, соединенные дорогами перед реформой. Следующие \textbf{q} cтрок содержат по три элемента, разделенные пробелами. "\textbf{+ i j}" означает строительство дороги от города \textbf{i} до города \textbf{j}, "\textbf{- i j}" означает закрытие дороги от города \textbf{i} до города \textbf{j}, "\textbf{? i j} " означает запрос об оптимальном пути между городами \textbf{i} и \textbf{j}.
Гарантируется, что в начале и после каждого изменения никакие два города не соединены более чем одной дорогой, и из каждого города выходит не более двух дорог. Никакой город не соединен дорогой сам с собой.
\OutputFile
На каждый запрос вида "\textbf{? i j}" выведите одно число - минимальное количество промежуточных городов на маршруте из города \textbf{i} в город \textbf{j}. Если проехать из \textbf{i} в \textbf{j} невозможно, выведите \textbf{-1}.
Входные данные #1
5 4 6 1 2 2 3 1 3 4 5 ? 1 2 ? 1 5 - 2 3 ? 2 3 + 2 4 ? 1 5
Выходные данные #1
0 -1 1 2