## Find a \$\log_2(|V|)\$ long cycle where each node is of different color

Here’s a question from an algorithms exam by Prof. Noga Alon that I just can’t wrap my head around.

Let $$G=(V,E)$$ be a directed graph where $$|V|=n$$. Let $$k=\lfloor \log_2(n)\rfloor$$. Each node in the graph is in one of $$k$$ colors. Give an efficient algorithm to determine if there exists a simple cycle of length $$k$$ in the graph where each node has a different color.

I really don’t know where to start with this. I thought about breaking the graph into subsets of nodes of each color and having multiple copies of each subsets in order to force a color change with every edge we traverse but I couldn’t get this to work. Any hint is appreciated!