Count Bridges

Limits 2s, 512 MB

You are given an unweighted, undirected, and connected graph consisting of NN nodes and MM edges. You have to answer QQ queries on this graph. For each query, you will be given two nodes AA and BB. You have to find the number of Bridge(s)Bridge(s) in the shortest path from node AA to node BB.

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).


The first line of input will consist of three integers NN, MM, and QQ (3N,M,Q2×105)(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 MM lines consists of two distinct integers UU and VV (1U,VN)(1 ≤ U,V ≤ N) denoting there is an edge between node UU and node VV. There will not be any self-loop or multiple edges in the graph.

The following QQ lines consist of two distinct integers AA and BB (1A,BN)(1 ≤ A, B ≤ N) representing the queries.


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


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