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