The Rainbow Bridge

An archipelago has N islands, each with a specific color. Bridges are built between islands one by one. A 'Rainbow Path' exists within a connected component if that component contains at least 3 distinct island colors. Given the colors of each island and the sequence of M bridges, find the index (1-based) of the first bridge that creates a Rainbow Path. If no such path is ever formed, output -1. Example: Input: 5 3 0 1 0 2 1 0 1 2 3 0 2 Colors: Island 0=col 0, 1=col 1, 2=col 0, 3=col 2, 4=col 1. Bridge 1 (0-1): {0,1} has colors {0,1}. Bridge 2 (2-3): {2,3} has colors {0,2}. Bridge 3 (0-2): {0,1,2,3} has colors {0,1,2}. BINGO! Output: 3