http://mirror.codeforces.com/gym/100496

I have used a O(unknown) approach and got AC 1700ms:

first,choose a valid root node and perform bfs(),foreach node in the queue list judge and color the node in order from 1 to n...

the implement of bfs() is O(n*log(n)) but the main problem is how to choose valid root and prove its correctness that I have no idea,so I enum each node as root node,if there is valid solution break.

and 1700ms AC, maybe there are a lot of valid root nodes...

can anyone give prove or better idea???