Help with INOI graph problem

How can I solve this problem SEQUENCE LAND from INOI 13?

My initial approach was to check every possible pair of relatives and then do a dfs on the king and find the size of the graph. But to check for relatives it took me O(n^4) time - . To speed it up I tried using binary search O(n^3 logn) but that doesn’t seem to work for some reason can anybody find out the problem in my binary search code or suggest a better way to solve this problem?