Google | L4 | Phone Screen | Rejected

I had a screening round and was asked this question:

Given an undirected acyclic graph with all of the vertices   
having at most 3 neighbors.   
Every vertex is colored either   
in red or black or white.   
Please find a root vertex so that:  
  
1. It will form a valid binary tree.  
2. Vertices with the same depth are colored with the same color.  
3. Color should be changing   
in R->W->B->R->W->B order as depth increases.   
Please note that R->B->W->R->B->W is not allowed.   
(root can be any color,   
so it can be R->W->B->… or W->B->R->…   
or B->R->W->… starting from root)  
  
  
Return -1 if we can’t find such a vertex.  

My Approach : Approach was start from any node do simple bfs, at each step I will validate whether it's neighbour can be a child [max two count ]or parent based on given color order. If it is not following simply return -1 else will mark parent of each node based on color order in an array initially initialized as -1 for all. At last ,the one which has it's parent as -1 will be my rootIndex.
Time Complexity : O(N).

Could not complete the code as Interviewer was not satisfied with Input structure used for graph reperesentation.

Can Someone share working code with proper data structure for graph reperesentation.