I think this is possible. Initially I started writing some dp with O(2^n * n * 2^n * something_for_the_bigraph). It is too complex for a problem that can be solved using only a dfs. But the idea is still good!