The Cultural Protocol

In a social network, every person has a 'Culture' (e.g., A, B, or C). A diplomat needs to pass a message from person S to person T. However, to respect protocol, the message must pass through at least one person of Culture 'A', then at least one person of Culture 'B', and then at least one person of Culture 'C', in that exact order (other cultures can be visited in between). Is there a path from S to T that satisfies this? Input Format: - Line 1: N M (People, Connections). - Line 2: N characters representing the culture of each person (0 to N-1). - Line 3: S T (Start, Target). - Next M lines: U V (undirected connection). Output Format: - 'VALID' or 'INVALID'. Example: Input: 5 5 A C B A C 0 4 0 1 1 2 2 3 3 4 0 3 Output: VALID (Explanation: Path 0(A) -> 1(C) -> 2(B) -> 4(C) satisfies the sequence A -> B -> C.)