Задачі
Ех, дороги...
Ех, дороги...
У багатостраждальному Тридесятому царстві знову готується дорожня реформа. Втім, потрібно визнати, дороги у цьому царстві знаходяться у досить плачевному стані. Так що реформа не зашкодить. Одна проблема - "дорожникам не розгорнутись, оскільки в країні діє жорсткий закон" - з кожного міста повинно виходити не більше двох доріг. Всі дороги у державі двостронні, тобто по ним дозволено рух в обох напрямках (зразуміло, розмітка відсутня). В результаті реформи деякі дороги будуть будуватись, а деякі інші закриватись на довготривалий ремонт.
Петро працює диспетчером у службі вантажоперевезень на далекі відстані. У зв'язку з майбутніми реформами, йому необхідно оперативно визначати оптимальні маршрути між містами в умовах постійно змінюваної дорожної ситуації. Через велику кількість заторів і працівник поліції в містах, критерієм оптимальності маршруту вважається кількість проміжних міст, які потрібно проїхати.
Допоможіть Петру за заданою послідовністю повідомлень про зміни структури доріг і запитам про оптимальний спосіб проїзду з одного міста в інше, оперативно відповідати на запити.
\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} рядків містять по три елементи, відокремлені пропусками. "\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