Give an undirected graph $G=(V,E)$ with $n$ vertices and $m$ edge,

and a positive $($not necessarily unique$)$ edge cost $C_e$ for each

edge in $E.$ We also given q pairs of vertices Q $=\{($u$1,$ v$1),...,($uq$,$ vq$)\}.$ Decide for each pair $(u,v)$ in $Q$ if there is a path between $u$ and $v$ in $G.$

Task: Design an algorithm that solves this problem in $O(q*(m+n))$

time.

Implementation and Testing: Implement your algorithm and

test it on the following graph instances: Graph $8,$ Graph $250,$

Graph $1000.$ Each instance is given as a text file using the

following format:

n

m

vertexId vertexId weight

vertexId vertexId weight

$...$

vertexId vertexId weight

$q$

vertexId vertexId

vertexId vertexId

$...$

For example, the text below describes the instance depicted in Fig. $1.$

Note that the vertices are numbered from $0$ to $n-1$ and that

the two queries are $(0,1)$ and $(0,2).$

$4$

$3$

$022$

$035$

$233$

$2$

$01$

$02$

Your program should read input from the text file. Your program

only needs to print out $\text{'}1\text{'}(=$yes, there is a path in $G$ between

$u$ and $v)$ or $\text{'}0\text{'}($there is no path connecting $u$ and $v$ in $G)$

for each of the $q$ query pairs. You should separate each $1/0$

with a new line. A scaffold is provided for Python.

Your code will not be benchmarked or tested for time complexity, but

for full point it must be able to run instances similar to

"Graph $1000,$ and each test will time out after $5$ seconds.

Your program will also be tested on serveral hidden test cases.

If the query is $(0,1)$ on the figure $1$ below then the answer

should be $\text{'}0\text{'},$ while the answer to the query $(0,2)$ on the same

graph should be $\text{'}$I$\text{'}.$

Figure I: Illustrating the graph described in $Q_1,$ with $n=4$ and $m=3.$

python code don't using ai