eolymp
bolt
Try our new interface for solving problems
Problems

Эх, дороги...

Эх, дороги...

Time limit 2 seconds
Memory limit 64 MiB

В многострадальном Тридесятом государстве опять готовится дорожная реформа. Впрочем, надо признать, дороги в этом государстве находятся в довольно плачевном состоянии. Так что реформа не повредит. Одна проблема - "дорожникам не развернуться, поскольку в стране действует жесткий закон" - из каждого города должно вести не более двух дорог. Все дороги в государстве двустронние, то есть по ним разрешено движение в обеих направлениях (разумеется, разметка отсутствует). В результате реформы некоторые дороги будут строиться, а некоторые другие закрываться на бессрочный ремонт.

Петя работает диспетчером в службе грузоперевозок на дальние расстояния. В связи с предстоящими реформами, ему необходимо оперативно определять оптимальные маршруты между городами в условиях постоянно меняющейся дорожной ситуации. В силу большого количества пробок и сотрудников полиции в городах, критерием оптимальности маршрута считается количество промежуточных городов, которые необходимо проехать.

Помогите Пете по заданной последовательности сообщений об изменении структуры дорог и запросам об оптимальном способе проезда из одного города в другой, оперативно отвечать на запросы.

Input data

В первой строке входного файла заданы числа n - количество городов, m - количество дорог в начале реформы и q - количество сообщений об изменении дорожной структуры и запросов (1n, m100 000, q200 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

Input example #1
5 4 6
1 2
2 3
1 3
4 5
? 1 2
? 1 5
- 2 3
? 2 3
+ 2 4
? 1 5
Output example #1
0
-1
1
2
Author В.Гольдштейн
Source Зимние сборы в Харькове 2010 День 2