# Count Bridges

Cefalo SUST Inter Univers...
Limits 2s, 512 MB

You are given an unweighted, undirected, and connected graph consisting of $N$ nodes and $M$ edges. You have to answer $Q$ queries on this graph. For each query, you will be given two nodes $A$ and $B$. You have to find the number of $Bridge(s)$ in the shortest path from node $A$ to node $B$.

In graph theory, a bridge or cut-edge is an edge of a graph whose deletion increases the number of connected components in that graph.

A connected component is a set of vertices in a graph that are linked to each other by path(s).

## Input

The first line of input will consist of three integers $N$, $M$, and $Q$ $(3 ≤ N, M, Q ≤ 2 × 10^5 )$ representing the number of nodes, the number of edges, and the number of queries, respectively.
Each of the next $M$ lines consists of two distinct integers $U$ and $V$ $(1 ≤ U,V ≤ N)$ denoting there is an edge between node $U$ and node $V$. There will not be any self-loop or multiple edges in the graph.

The following $Q$ lines consist of two distinct integers $A$ and $B$ $(1 ≤ A, B ≤ N)$ representing the queries.

## Output

For each query, you have to print the total number of bridge(s) in any of the shortest path(s) from node $A$ to node $B$ in separate lines.

## Sample

InputOutput
7 7 4
1 3
1 2
2 4
2 5
4 6
5 6
6 7
1 7
2 6
3 7
1 4

2
0
3
1