You are given a directed graph G in which edges are labelled using labels from {1,2,3,4}. A sequence of vertices v1 ... vk (which may contain duplicates) is defined to be ``reversible'' if (a) v1-v2, v2-v3, etc. form edges, and (b) the label of these edges, written as a string in the order they appear in the sequence, is equal to its reverse. For example, v1-v2-v3-v1-v2 with label(v1-v2)=2, label(v2-v3)=3, label(v3-v1)=3, form a reversible sequence. For simplicity, assume that sequences like 'u' (only one vertex) are reversible.
Given two vertices s and v, design an algorithm to determine the length of the shortest reversible sequence starting and ending at s and t, respectively, or report that no such sequence is possible. You can use the fact that if any such sequence is present, it will use at most O(n^4) edges.
If you are designing a DP, give all 7 steps. If you are reducing this to a graph problem, follow the usual steps of graph reduction. In none of the approaches, a pseudocode should be provided.