Let $G=(UV,E)$ be a bipartite network, with $U=\{u_1,$dots,$u_n\}.$

$($a$)$ Give an algorithm for determining if there exists a matching such that, for each consecutive pair $u_i,u_{i+1},$ at least one of $u_i$ and $u_{i+1}$ is matched to a vertex in $V.$

$($b$)$ GIve an algorithm for finding the largest possible matching such that, for each consecutive pair $u_i,u_{i+1},$ at most one of $u_i$ and $u_{i+1}$ is matched to a vertex in $V.$