Road Reform#690
In the Thrice-Ninth Kingdom, a new road reform is being planned. The roads in this kingdom are in poor condition, so this reform is much needed. However, there is a strict law: no more than two roads can exit any city. All roads are bidirectional, i.e., travel is allowed in both directions. As a result of the reform, some roads will be constructed and others will be closed for long-term repairs.
Peter is a dispatcher in long-distance freight transport. With the upcoming reforms, he needs to quickly determine optimal routes between cities as the road network constantly changes. Due to frequent traffic jams and police officers in the cities, the optimal route is determined by the number of intermediate cities that need to be passed through.
Help Peter quickly respond to queries regarding changes in the road structure and requests for finding optimal routes between cities.
The first line contains — the number of cities, — the number of roads before the reform, and — the number of queries for changes and route requests (1 \le n, m \le 100\ 000, q \le 200\ 000). The next lines each contain two integers, meaning the pairs of cities that are directly connected by a road before the reform. The following lines each contain three items separated by spaces. "+ i j" means constructing a road between city and city ; "- i j" means closing the road between city and city ; "? i j" is a query for the optimal route between cities and .
It is guaranteed that at the start and after each change, no two cities are connected by more than one road, and each city has at most two roads leading out of it. No city is connected to itself by a road.
For each query of the form "? i j", output a single number — the minimum number of intermediate cities on the route from city to city . If it is impossible to travel from to , output .
Example 1