EOPERA с SPOJ

Давно ломаю голову над

http://www.spoj.pl/problems/EOPERA/

bfs явно не подойдет - слишком много состояний.  Как-то наверное надо сортировать по половинам, но тоже не понятно как.
поделитесь мыслями плз