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