Ех, дороги...
У багатостраждальному Тридесятому царстві знову готується дорожня реформа. Втім, потрібно визнати, дороги у цьому царстві знаходяться у досить плачевному стані. Так що реформа не зашкодить. Одна проблема - "дорожникам не розгорнутись, оскільки в країні діє жорсткий закон" - з кожного міста повинно виходити не більше двох доріг. Всі дороги у державі двостронні, тобто по ним дозволено рух в обох напрямках (зразуміло, розмітка відсутня). В результаті реформи деякі дороги будуть будуватись, а деякі інші закриватись на довготривалий ремонт.
Петро працює диспетчером у службі вантажоперевезень на далекі відстані. У зв'язку з майбутніми реформами, йому необхідно оперативно визначати оптимальні маршрути між містами в умовах постійно змінюваної дорожної ситуації. Через велику кількість заторів і працівник поліції в містах, критерієм оптимальності маршруту вважається кількість проміжних міст, які потрібно проїхати.
Допоможіть Петру за заданою послідовністю повідомлень про зміни структури доріг і запитам про оптимальний спосіб проїзду з одного міста в інше, оперативно відповідати на запити.
Вхідні дані
У першому рядку вхідного файлу задані числа n - кількість міст, m - кількість доріг на початку реформи і q - кількість повідомлень про зміни дорожної структури і запитів (1 ≤ n, m ≤ 100 000, q ≤ 200 000). Наступні m рядків містять по два цілих числа кажен - пари міст, з'єднаних дорогами перед реформою. Наступні q рядків містять по три елементи, відокремлені пропусками. "+ i j" означає будівництво дороги від міста i до міста j, "- i j" означає закриття дороги від міста i до міста j, "? i j " означає запит про оптимальний шлях між містами i та j.
Гарантується, що на початку і після кожної зміни ниякі два міста не з'єднані більше ніж однією дорогою, і з кожного міста виходить не більше двох доріг. Ніяке місто не з'єднано дорогою саме з собою.
Вихідні дані
На кажен запит виду "? i j" виведіть одне число - мінімальну кількість проміжних міст на маршруті з міста i в місто j. Якщо проїхати з i в j неможливо, виведіть -1.