Counting Critical Routes

On the Samuel galaxy, scientists have mapped n planets along with their exploration routes. Each route connects two planets bidirectionally. Due to cosmic disturbances, some routes may be destroyed over time. For any two planets A and B, an existing route is called critical if its removal disconnects A and B in the current network. Formally, an edge \(e\) is critical for vertices \(u\) and \(v\) if and only if \(u\) and \(v\) are connected in the current graph, but deleting \(e\) makes them disconnected.

Your task is to process a sequence of operations on the exploration network. Initially, the Samuel system provides m exploration routes between n planets (numbered from 1 to \(n\)). Then, a series of operations follow. Each operation is either a destruction of an existing route or a query asking for the number of critical routes between two given planets.

Note: When the queried planets are not connected (i.e. there is no route connecting them), output 0.

The problem may be solved by recomputing the bridges (using Tarjan's algorithm, for instance) and then, by contracting the graph into its 2-edge-connected components. The unique path in the resulting tree between the components of the queried planets gives the number of critical edges.

All formulas are given in \(\LaTeX\) format.

inputFormat

The input begins with a line containing three integers \(n\), \(m\), and \(q\) representing the number of planets, the number of initial exploration routes, and the number of operations, respectively. The next \(m\) lines each contain two integers \(u\) and \(v\) (1 ≤ \(u, v\) ≤ \(n\)), indicating an exploration route between planet \(u\) and planet \(v\). Following that, there are \(q\) lines, each describing an operation in one of the following formats:

• D u v: Destroy (remove) the exploration route between planets \(u\) and \(v\). It is guaranteed that this route exists at the time of destruction.
• Q u v: Query the number of critical routes between planets \(u\) and \(v\) in the current network.

If the two planets are not connected in the current graph, output 0 in the query result.

outputFormat

For each query operation, output a single line containing an integer representing the number of critical routes between the two specified planets.

sample

5 5 3
1 2
1 3
2 4
3 4
4 5
Q 1 5
D 2 4
Q 1 5

1
3