Oh, the roads...
In the long-suffering Thrice-Tenth Kingdom, a new road reform is underway. The roads in this kingdom are in a rather poor condition, so the reform is much needed. However, there is a strict law in place: no more than two roads can lead out of each city. All roads are bidirectional, allowing traffic in both directions, and there are no road markings. As part of the reform, some roads will be built, while others will be closed for long-term repairs.
Peter is a dispatcher for the long-distance freight service. With the upcoming reforms, he needs to quickly determine the best routes between cities as the road network changes. Given the frequent traffic jams and police presence in the cities, the optimal route is defined by the number of intermediate cities that must be traversed.
Help Peter respond swiftly to requests by finding the best way to travel between cities, based on a sequence of messages about changes in the road network and route requests.
Input
The first line of the input contains three numbers: n - the number of cities, m - the number of roads at the start of the reform, and q - the number of messages about changes in the road network and route requests (1 ≤ n, m ≤ 100,000, q ≤ 200,000). The following m lines each contain two integers, representing pairs of cities connected by roads before the reform. The next q lines each contain three elements, separated by spaces: "+ i j" indicates the construction of a road between city i and city j, "- i j" indicates the closure of a road between city i and city j, and "? i j" is a request for the optimal path between cities i and j.
It is guaranteed that at the start and after each change, no two cities are connected by more than one road, and no city has more than two roads leading out of it. No city is connected by a road to itself.
Output
For each request of the form "? i j", output a single number - the minimum number of intermediate cities on the route from city i to city j. If it is impossible to travel from i to j, output -1.