You are given an unweighted, undirected, and connected graph consisting of nodes and edges. You have to answer queries on this graph. For each query, you will be given two nodes and . You have to find the number of in the shortest path from node to node .
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 , , and representing the number of nodes, the number of edges, and the number of queries, respectively.
Each of the next lines consists of two distinct integers and denoting there is an edge between node
and node . There will not be any self-loop or multiple edges in the graph.
The following
lines consist of two distinct integers and 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 to node 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 |