Unique paths

0

0 votes
Bridges, Algorithms, Articulation Points and Bridges, Graphs, Graph, Disjoint Set
Problem

You are given a connected undirected graph containing N nodes and M edges. The task is very simple. You are provided two nodes u and v. You are required to check whether the path from u to v is unique or not. If there exists a path, you are required to determine the distance between the nodes u and v, then print 1. You must perform these operations for Q queries. 

Input format

  • First line: Two space-separated integersN and M 
  • Next M lines: Two space-separated integers u and v denoting that there is an edge between node u and v
  • Next line contains a single integer Q  denoting the number of queries
  • Next Q lines: Two space-separated integers u and v

Output format

For each query, print the distance between the two nodes if there exists a unique path between the nodes in that query. Otherwise, print 1.

Constraints

2N105N1Mmin(105,N(N1)2)1u,vN$$1Q105 

The provided graph is connected and it does not contain self-loops and multiple edges.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Only one unique path exists in the given graph. It is from 1 to 2. The distance between them is 1

Editor Image

?