Eh, yollar...
Üçüncü Krallıqda yenidən yol islahatı planlaşdırılır. Bu krallığın yolları çox pis vəziyyətdədir, buna görə də islahat faydalı ola bilər. Lakin bir problem var: "yolları genişləndirmək mümkün deyil, çünki ölkədə sərt qanun qüvvədədir" - hər şəhərdən ən çox iki yol çıxmalıdır. Bütün yollar ikitərəflidir, yəni hər iki istiqamətdə hərəkət mümkündür. İslahat nəticəsində bəzi yollar tikiləcək, bəziləri isə uzunmüddətli təmirə bağlanacaq.
Peyğəmbər uzaq məsafələrə yükdaşıma xidmətində dispetçer işləyir. Gələcək islahatlarla əlaqədar olaraq, o, daim dəyişən yol şəraitində şəhərlər arasında optimal marşrutları tez bir zamanda müəyyən etməlidir. Çoxlu tıxaclar və şəhərlərdə polis işçiləri səbəbindən marşrutun optimallıq meyarı keçilməli olan aralıq şəhərlərin sayıdır.
Peyğəmbərə yol strukturunun dəyişiklikləri və bir şəhərdən digərinə optimal keçid üsulu ilə bağlı sorğuların ardıcıllığına görə sorğulara operativ cavab verməyə kömək edin.
Giriş verilənləri
Giriş faylının ilk sətirində n - şəhərlərin sayı, m - islahatın əvvəlindəki yolların sayı və q - yol strukturunun dəyişiklikləri və sorğuların sayı (1 ≤ n, m ≤ 100 000, q ≤ 200 000) verilmişdir. Növbəti m sətir hər biri iki tam ədəd olan - islahatdan əvvəl yollarla birləşdirilmiş şəhər cütlərini ehtiva edir. Növbəti q sətir hər biri boşluqla ayrılmış üç elementdən ibarətdir. "+ i j" şəhər i-dən şəhər j-ə yol tikintisini, "- i j" şəhər i-dən şəhər j-ə yolun bağlanmasını, "? i j" şəhərlər i və j arasında optimal yol sorğusunu ifadə edir.
Zəmanət verilir ki, əvvəl və hər bir dəyişiklikdən sonra heç bir iki şəhər bir yoldan artıq birləşdirilməyəcək və hər şəhərdən ən çox iki yol çıxacaq. Heç bir şəhər özü ilə yol ilə birləşdirilməyib.
Çıxış verilənləri
"? i j" tipli hər bir sorğuya bir ədəd çıxarın - şəhər i-dən şəhər j-ə marşrutda minimum aralıq şəhərlərin sayı. Əgər i-dən j-ə keçmək mümkün deyilsə, -1 çıxarın.