Problem $3.$ Let G$=($V$,$E$)$ be a connected, undirected graph. We start with coins placed on arbitrarily chosen vertices of G$,$ and each coin can move to an adjacent vertex at every step. The objective is to determine if it is possible to bring all coins to the same vertex, and if so$,$ compute the minimum number of moves required.

$($a$)$ Suppose there are two coins placed on two given vertices u$,$v in V$,$ which may or may not be distinct. Describe and analyze an algorithm to compute the minimum number of steps to reach a configuration where both coins are on the same vertex, or to report correctly that no such configuration is possible. The input to your algorithm consists of the graph G$=($V$,$E$)$ and the initial vertices u and v$.$

$($b$)$ Now suppose there are three coins placed on three given vertices of G$.$ Describe and analyze an algorithm to compute the minimum number of steps to reach a configuration where all three coins are on the same vertex, or to report correctly that no such configuration is possible.

$($c$)$ Finally, suppose there are forty$-$two coins placed on forty$-$two given vertices of G$.$ Describe and analyze an algorithm to determine whether it is possible to move all $42$ coins to the same vertex. For full credit, your algorithm should run in O$($V$+$E$)$ time.

Prove the correctness of your algorithms and analyze their running time $($or any other efficiency measure asked in the question$).$ Solve the question in detail. Show each and every step.